Cod sursa(job #1746223)

Utilizator antanaAntonia Boca antana Data 22 august 2016 21:42:03
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include<string.h>
#define MAXN 1000000

char aux[MAXN+1], s[2*MAXN+2];
int n, p[2*MAXN+1], np;
long long ans;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    int r=0, c=0;

    gets(aux);
    n=strlen(aux);

    s[0]='*';
    for(int i=0;i<n;++i)
        s[2*i+1]=aux[i], s[2*i+2]='*';
    np=2*n;

    for(int i=1;i<=np;++i)
    {
        if(i>r) p[i]=0;
        else
        {
            if(p[2*c-i] > r-i)
                p[i]=r-i;
            else p[i]=p[2*c-i];
        }
        while(i+p[i]+1 <=np && i-p[i]-1 >=0 && s[i+p[i]+1]==s[i-p[i]-1])
            p[i]++;

        if(i+p[i] > r)
        {
            r=i+p[i];
            c=i;
        }
        ans+=(p[i]+1)/2;
    }
    printf("%lld", ans);

    return 0;
}