Pagini recente » Cod sursa (job #1877415) | Cod sursa (job #977433) | Cod sursa (job #2947946) | Cod sursa (job #2956383) | Cod sursa (job #1746223)
#include <cstdio>
#include<string.h>
#define MAXN 1000000
char aux[MAXN+1], s[2*MAXN+2];
int n, p[2*MAXN+1], np;
long long ans;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int r=0, c=0;
gets(aux);
n=strlen(aux);
s[0]='*';
for(int i=0;i<n;++i)
s[2*i+1]=aux[i], s[2*i+2]='*';
np=2*n;
for(int i=1;i<=np;++i)
{
if(i>r) p[i]=0;
else
{
if(p[2*c-i] > r-i)
p[i]=r-i;
else p[i]=p[2*c-i];
}
while(i+p[i]+1 <=np && i-p[i]-1 >=0 && s[i+p[i]+1]==s[i-p[i]-1])
p[i]++;
if(i+p[i] > r)
{
r=i+p[i];
c=i;
}
ans+=(p[i]+1)/2;
}
printf("%lld", ans);
return 0;
}