Cod sursa(job #1320742)

Utilizator felixiPuscasu Felix felixi Data 18 ianuarie 2015 14:16:12
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <string>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

typedef long long i64;

const int nmax= 1000000;

string s, v;

int p[nmax*2+1];

int main(  ) {
    fin>>s;
    int n= s.size();
    for ( int i= 0; i<n; ++i ) {
        v+='$'; v+=s[i];
    }
    v+='$';
    n= v.size();

    int c= 0;
    for ( int i= 0; i<n; ++i ) {
        int aux= 0;
        if ( c+p[c]>=i ) {
            aux= min(p[2*c-i], c+p[c]-i);
        }

        while ( i-aux-1>=0&& i+aux+1<n&& v[i-aux-1]==v[i+aux+1] ) {
            ++aux;
        }

        p[i]= aux;
        if ( c+p[c]<i+p[i] ) {
            c= i;
        }
    }

    i64 sol= n/2;
    for ( int i= 0; i<n; ++i ) {
        sol+= p[i]/2;
    }
    fout<<sol<<"\n";

    return 0;
}