Pagini recente » Cod sursa (job #2283400) | Cod sursa (job #2485080) | Cod sursa (job #1869866) | Cod sursa (job #832372) | Cod sursa (job #1623459)
#include <fstream>
#include <string>
using namespace std;
#define Nmax 2000002
ifstream fin ( "pscpld.in" );
ofstream fout ( "pscpld.out" );
string A, S;
int P[Nmax];
long long Manacher(){
long long Sum = 0;
int 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;
}