Pagini recente » Cod sursa (job #770315) | Cod sursa (job #268492) | Cod sursa (job #2312370) | Cod sursa (job #1624193) | Cod sursa (job #1623436)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define Nmax 2000002
ifstream fin ( "pscpld.in" );
ofstream fout ( "pscpld.out" );
string A, S;
int P[Nmax];
int Manacher(){
int Sum = 0, C = 0, R = 0;
for ( int i = 1; i < S.size() - 1; ++i ){
int ip = 2 * C - i;
P[i] = ( R > i ) ? min ( R-i, P[ip] ) : 0;
while ( S[i+1+P[i]] == S[i-1-P[i]] )
P[i]++;
if ( i + P[i] > R ){
C = i;
R = i + P[i];
}
Sum += (P[i]+1)/2;
}
return Sum;
}
int main(){
fin >> A;
for ( int i = 0; i < A.size(); ++i )
S += "#" + A.substr(i,1);
S += "#";
fout << Manacher();
return 0;
}