Pagini recente » Cod sursa (job #1255277) | Cod sursa (job #1251700) | Cod sursa (job #1609860) | Cod sursa (job #2282130) | Cod sursa (job #1003986)
#include<stdio.h>
#include<string.h>
char s[2000002],v[2000002];
int m[2000002];
inline void ext(int i)
{
while(s[i-m[i]-1]==s[i+m[i]+1]&&m[i]<i)
++m[i];
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
int n,i,l=0,sol=0,p=0;
scanf("%s",&v);
n=strlen(v);
s[0]='*';
for(i=0;i<n;++i)
{
s[++p]=v[i];
s[++p]='*';
}
n=p;
////////////////
for(i=1;i<=n;++i)
{
if(l+m[l]<i)
ext(i);
else if(l-m[l]>=2*l-i-m[2*l-i])
{
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);
//printf("%s",s);
return 0;
}