Cod sursa(job #893785)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 26 februarie 2013 17:53:08
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstring>
#include<cstdio>
#define NMAX 1000000+5
using namespace std;
char s[NMAX];
int i,j,l,r,p[2*NMAX],q[2*NMAX],n;
long long sol;
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    s[0]='*'; s[n+1]='#';
    p[1]=1;
    if(s[1]==s[2]) p[2]=2;
    for(i=3;i<=2*n-1;i++)
    {
        if(i%2==0) //palindrom de lungime para
        {
            if(q[i]) {l=(i-p[q[i]]+2)/2; r=p[q[i]]-1+l;}
            else {l=i/2; r=i/2+1;}
        }
        else //palindrom de lungime impara
        {
            if(q[i]) {l=(i-p[q[i]]+2)/2; r=p[q[i]]-1+l;}
            else l=r=i/2;
        }
        for(;s[l]==s[r];l--,r++)
        {
            if(p[2*l-1]>p[q[2*r-1]]) q[2*r-1]=2*l-1;
            if(p[2*l]>p[q[2*r]]) q[2*r]=2*l;
        }
        l++, r--;
        p[i]=r-l+1;
        sol+=(p[i]+1)/2;
    }
    /*for(i=1;i<=2*n-1;i++) printf("%d ",p[i]);
    printf("\n");
    for(i=1;i<=2*n-1;i++) printf("%d ",q[i]);
    printf("\n");*/
    printf("%lld\n",sol+1);
    return 0;
}