Cod sursa(job #1623440)

Utilizator BLz0rDospra Cristian BLz0r Data 1 martie 2016 19:33:33
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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.push_back('#');
        S.push_back(A[i]);
    }
    S.push_back('#');

    fout << Manacher();

    return 0;
}