Cod sursa(job #834376)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int NMAX=2000005;
char S[NMAX],T[NMAX];
int best[NMAX];
long long ret;
int N,M;
void read () {
fgets (S,NMAX,stdin);
N=strlen (S)-(S[strlen (S)-1]=='\n');
T[++M]='#';
for (int i=0; i<N; ++i) {
T[++M]=' ';
T[++M]=S[i];
}
T[++M]=' '; T[++M]='$';
}
void solve () {
int C,R;
C=R=0;
for (int i=1; i<M; ++i) {
int mirror_i=2*C-i;
if (i<R)
best[i]=min (R-i,best[mirror_i]);
while (T[i-best[i]-1]==T[i+best[i]+1])
++best[i];
if (i+best[i]>R) {
C=i;
R=i+best[i];
}
ret+=(best[i]+1)/2;
}
cout<<ret;
}
int main () {
freopen ("pscpld.in","r",stdin);
freopen ("pscpld.out","w",stdout);
read ();
solve ();
return 0;
}