Cod sursa(job #894421)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 26 februarie 2013 21:13:59
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<cstdio>
#include<cstring>
using namespace std;
const int SMAX=1000005;
int n,i,j,P[SMAX*2],M[SMAX*2],l,r,N;
long long sol;
char a[SMAX],S[SMAX*2];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",a+1); n=strlen(a+1);
    for(i=1;i<=n;i++)
    {
        S[++N]=a[i]; P[N]=1;
        S[++N]=' ';
    }
    for(i=1;i<=N-1;i++)
    {
        if(M[i]) P[i]=P[2*M[i]-i];
        l=i; r=i; l--; r++; l-=P[i]; r+=P[i];
        while(l>=1 && r<=N && S[l]==S[r]) P[i]+=2,M[r]=M[r-1]=i,l-=2,r+=2;
        sol+=(P[i]+1)/2;
    }
    //for(i=1;i<=N-1;i++) printf("%d ",P[i]);
    printf("%lld\n",sol);
    return 0;
}