Pagini recente » Cod sursa (job #1555445) | Cod sursa (job #834368)
Cod sursa(job #834368)
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int NMAX=1000005;
unsigned int best[NMAX];
long long ret;
string S,T;
void read () {
cin>>S;
T="#";
for (unsigned int i=0; i<S.length (); ++i) {
T+=" ";
T+=S[i];
}
T+=" $";
}
void solve () {
unsigned int C,R;
C=R=0;
for (unsigned int i=1; i<T.length ()-1; ++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;
}