Cod sursa(job #1957877)

Utilizator LucianTLucian Trepteanu LucianT Data 7 aprilie 2017 20:29:37
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
// Manacher
#include <bits/stdc++.h>
#define maxN 1000005
using namespace std;
int n,i,idx,len[2*maxN];
char aux[maxN],str[2*maxN];
long long sol;
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    gets(aux+1);
    n=strlen(aux+1);

    for(i=1;i<=n;i++)
        str[2*i-1]='$',str[2*i]=aux[i];
    str[n=2*n+1]='$';

    int idx=0;
    int center=0;
    for(i=1;i<=n;i++)
    {
        if(i<=idx)
            len[i]=min(idx+1-i,len[center-(i-center)]);

        while(i+len[i]<=n && i-len[i]>=1 && str[i+len[i]]==str[i-len[i]])
            len[i]++;

        if(i+len[i]-1>idx){
            idx=i+len[i]-1;
            center=i;
        }

        sol+=len[i]/2;
    }
    printf("%lld",sol);
    return 0;
}