Cod sursa(job #981178)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 6 august 2013 15:29:28
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio> 
#include<cstring>
int n,d[2000010],i,b;
char v[2000010];
long long s; 
int main() 
{
    freopen("pscpld.in","r",stdin),
    freopen("pscpld.out","w",stdout),
    scanf("%s",v+1),
    n=strlen(v+1);
    for(i=2*n+1;i;i--)
    if(i%2)
          v[i]='#';
    else
          v[i]=v[i/2];
    n=2*n+1;
    for(i=1;i<=n;++i) 
    {
          if(b+d[b]>=i)
                 d[i]=(b+d[b]-i>d[2*b-i])?d[2*b-i]:(b+d[b]-i);
          while(i-d[i]>1&&i+d[i]+1<=n&&v[i-d[i]-1]==v[i+d[i]+1])
                 ++d[i];
          if(i+d[i]>=b+d[b])
                 b=i;
    }
    for(i=1;i<=n;++i)
    if(i%2)
          s+=d[i]/2;
    else
          s+=(d[i]+1)/2;
    printf("%lld",s);
}