Cod sursa(job #2958892)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 28 decembrie 2022 22:14:33
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
char s[1000000],q[2000010];
int rz[2000010];
int n,l,r;
int main()
{
    cin>>s;
    l=-1;
    r=-1;
    q[n++]='#';
    for(int i=0;s[i]!='\0';i++)
      {
          q[n++]=s[i];
          q[n++]='#';
      }
      q[n++]='\0';
      for(int i=0;i<n;i++)
      {
          if(i>r)
               rz[i]=0;
               else
                 rz[i]=min(r-i,rz[l+r-i]);
          while(i-rz[i]>=0 && q[i-rz[i]]==q[i+rz[i]])
              rz[i]++;
          rz[i]--;
          if(i+rz[i]>r)
           {
               r=i+rz[i];
               l=i-rz[i];
           }
      }
   int sum=0;
    for(int i=1;i<n;i=i+2)
         sum=sum+rz[i];
         cout<<sum;
    return 0;
}