Pagini recente » Cod sursa (job #2291141) | Cod sursa (job #2525673) | Cod sursa (job #1414415) | Cod sursa (job #2642150) | Cod sursa (job #1746220)
#include <cstdio>
#include<string.h>
#define MAXN 1000000
char aux[MAXN+1], s[2*MAXN];
int n, p[2*MAXN], np, ans;
inline int maxim(int a, int b)
{
if(a>b)
return a;
return b;
}
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("%d", ans);
return 0;
}