Cod sursa(job #893484)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 26 februarie 2013 15:58:58
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define min(a,b) a<b?a:b
int i,j,R,C,P[1000010],len;
long long SOL;
char S[1000100],*p;
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf(" %s",S+1);
    len=strlen(S+1);
    C=0;R=0;
    for(i=1;i<=len;i++)
    {
        j=2*C-i;
        if(i<R)
            P[i]=min(R-i,P[j]);
        else P[i]=0;
        while(S[i+P[i]+1]&&P[i]<i&&S[i+P[i]+1]==S[i-P[i]])P[i]++;
        if(i+P[i]>R)
        {
            C=i;
            R=i+P[i];
        }
        SOL+=P[i];
    }
    C=0;R=0;
    memset(P,0,sizeof(P));
    for(i=1;i<=len;i++)
    {
        j=2*C-i;
        if(i<R)
            P[i]=min(R-i,P[j]); else P[i]=0;
        while(P[i]<i&&S[i+P[i]]&&S[i+P[i]]==S[i-P[i]])P[i]++;
        if(i+P[i]>R)
        {
            C=i;R=i+P[i];
        }
        SOL+=P[i];
    }
    printf("%lld\n",SOL);
    return 0;
}