Cod sursa(job #1003514)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 30 septembrie 2013 20:50:47
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<string.h>
char s[2000005];
unsigned d[2000005];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    unsigned n,i,j,p,m=0;
    gets(s+1);
    n=strlen(s+1);
    for(i=n;i>=1;i--)
    {
    s[2*i]=s[i];
    s[2*i+1]='*';
    }
    n=2*n+1;
    s[1]='*';
    p=0;
    for(i=1;i<=n;i++)
    {
    if(i>d[p]+p)
    {
        for(j=1;j<i && s[i+j]==s[i-j] && i-j>0 && i+j<=n;j++);
        p=i;
        d[i]=j-1;
    }
    else
{
    if(2*p-i-d[2*p-i]>p-d[p])
    {
    d[i]=d[2*p-i];
    m=m+d[i]/2;
    if(s[i]!='*')
        m++;
    }
    else
    d[i]=p+d[p]-i+1;
    if(i+d[i]==p+d[p])
    {
        for(;s[i-d[i]]==s[i+d[i]] && i+d[i]<=n && i-d[i]>0;d[i]++);
        p=i;
        d[i]--;
    }
}
m=m+d[i]/2;
if(s[i]!='*')
m++;
    }
printf("%u ",m);
    return 0;
}