Pagini recente » Cod sursa (job #1220880) | Cod sursa (job #128139) | Cod sursa (job #3154123) | Cod sursa (job #821808) | Cod sursa (job #1295711)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000100
char ch[N],v[2*N];
long long distanta[2*N];
int main()
{
freopen("pscpld.in" , "r" , stdin);
freopen("pscpld.out", "w" , stdout);
register long long h=0,len,suma=0,k;
register long long imax=1,lgmax=1;
scanf("%s",ch+1);
len = strlen(ch+1);
v[0] = '!'; v[2*len] = '@'; h = len*2; distanta[1] = 1;
for(int i = 1; i <=len;++i) v[i*2-1] = ch[i];
for(register int i=1;i <= h;++i){
distanta[i] = min( imax + lgmax- i, distanta[2*imax-i] ) ;
k = distanta[i];
while( v[i - k ] == v[ i+ k ]) ++k;
distanta[i] = k;
if( i + distanta[i] > imax + lgmax ) imax = i , lgmax = distanta[i];
}
for(register int i = 1;i < h ; i+=2) suma += (distanta[i]+1)/2;
for(register int i = 2;i < h ; i+=2) suma += distanta[i] /2;
printf("%lld",suma);
return 0;
}