Pagini recente » Cod sursa (job #116499) | Cod sursa (job #1775208) | Cod sursa (job #1863124) | Cod sursa (job #422808) | Cod sursa (job #1295692)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000006
char ch[N],v[2*N];
long long h,st,dr,centru ,simetric ,len;
long long distanta[2*N];
int main()
{
freopen("pscpld.in" , "r" , stdin);
freopen("pscpld.out", "w" , stdout);
scanf("%s",ch+1);
len = strlen(ch+1);
v[0] = '!'; v[2*len] = '@';
for(int i = 1; i <=len;++i){
v[++h] = ch[i];
v[++h] = '#';
}
for(int i=1;i < h;++i)
if( i < dr ){
simetric = centru - ( i - centru);
if( distanta[simetric] + i - 1 < dr ) distanta[i] = distanta[simetric];
else{
distanta[i] = dr - i + 1;
st = i - distanta[i] + 1;
--st; ++dr;
while( v[st] == v[dr] ){ ++distanta[i]; ++dr; --st;}
--dr ; centru = i;
}
}else{
st=dr=i;
while( v[st] == v[dr] ){ ++distanta[i]; ++dr; --st;}
--dr;
centru = i;
}
int suma = 0;
for(int i = 1;i < h ; i+=2) suma += (distanta[i]+1)/2;
for(int i = 2;i < h ; i+=2) suma += distanta[i] /2;
printf("%d",suma);
return 0;
}