Cod sursa(job #2275713)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 3 noiembrie 2018 14:08:44
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

const int MAX=2e6+3;
char s[MAX],a[MAX];
int v[MAX],n;
long long suma=0;
int main()
{
    in>>s;
    n=strlen(s);

    for(int i=0;i<n;i++)
       a[(i+1)*2]=s[i];

    n=2*n+3;
    a[0]=a[n-1]='$';
    for(int i=1;i<=n-2;i=i+2) a[i]='#';



    int imax=1,lim=1;
     v[1]=1;
    for(int i=2;i<n-1;i++)
    {
         if(i==lim+1)
         {
             imax=i;
             while(a[i-v[i]]==a[i+v[i]]) v[i]++;
             lim=i+v[i]-1;
         }

         else
         {
             if(i+v[2*imax-i]-1<lim) v[i]=v[2*imax-i];
             else
             {
                  imax=i;
                 v[i]=lim-i+1;
                  while(a[i-v[i]]==a[i+v[i]]) v[i]++;
                  lim=i+v[i]-1;

             }
         }
    }

    for(int i=1;i<=n-2;i++) suma+=v[i]/2;
    out<<suma;
    return 0;
}