Pagini recente » Cod sursa (job #609469) | Cod sursa (job #113724) | Cod sursa (job #636637) | Cod sursa (job #173546) | Cod sursa (job #1962433)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define NMax 1000005
using namespace std;
int C,R,ii,dif,i,lps[2*NMax],N;
long long sum;
char s[NMax];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s",&s);
C=1;
lps[0]=0;
lps[1]=1;
N=strlen(s);
N=2*N+1;
for(i=2; i<N; ++i)
{
ii=2*C-i;
dif=R-i;
lps[i]=0;
if(dif>0)
lps[i]=min(dif,lps[ii]);
while(((i+lps[i])<N&&(i-lps[i])>0)&&(((i+lps[i]+1)%2==0)||(s[(i+lps[i]+1)/2]==s[(i-lps[i]-1)/2])))
lps[i]++;
if(i+lps[i]>R)
{
C=i;
R=i+lps[i];
}
}
for(i=1; i<N; i++)
{
if(lps[i]%2==0) sum+=lps[i]/2;
else sum+=lps[i]/2+1;
}
printf("%lld\n",sum);
return 0;
}