Pagini recente » Cod sursa (job #1555397) | Cod sursa (job #1555434) | Cod sursa (job #834369)
Cod sursa(job #834369)
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int NMAX=2000005;
unsigned int best[NMAX];
long long ret;
string S,T;
void read () {
cin>>S;
T.resize (S.length ()*2+3); T[0]='#';
for (unsigned int i=0; i<S.length (); ++i) {
T[2*i+1]=' ';
T[2*i+2]=S[i];
}
T[S.length ()*2+1]=' ';
T[S.length ()*2+2]='$';
}
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;
}