Pagini recente » Cod sursa (job #1840284) | Clasament oni_2017_cl10_ziua2 | Cod sursa (job #773691) | Cod sursa (job #2752634) | Cod sursa (job #1623440)
#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.push_back('#');
S.push_back(A[i]);
}
S.push_back('#');
fout << Manacher();
return 0;
}