Cod sursa(job #1623436)

Utilizator BLz0rDospra Cristian BLz0r Data 1 martie 2016 19:32:14
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#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;
}