Cod sursa(job #1003600)

Utilizator thewildnathNathan Wildenberg thewildnath Data 30 septembrie 2013 23:48:04
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<string.h>

char s[2000002];
int m[2000002];

inline void ext(int i)
{
    while(s[i-m[i]-1]==s[i+m[i]+1])
        ++m[i];
}

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    int n,i,l=0,sol=0;
    scanf("%s",&s);
    n=strlen(s);
    for(i=n-1;i>0;--i)
    {
        s[2*(i+1)]=s[i];
        s[2*i+1]='*';
    }
    s[1]='*';
    n=n*2;
    ////////////////
    for(i=1;i<=n;++i)
    {
        if(l+m[l]<i)
            ext(i);
        if(l+m[l]>=(l-(i-l))-m[l-(i-l)])
        {
            m[i]=m[l]-i+l;
            ext(i);
        }
        else
            m[i]=m[2*l-i];
        if(i+m[i]>l+m[l])
            l=i;
        sol+=(m[i]+1)/2;
    }
    printf("%d\n",sol);
    return 0;
}