Cod sursa(job #1019164)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 30 octombrie 2013 19:02:13
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 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= -1;
    for ( int i= 0; i<n; ++i ) {
        int aux;
        if ( c==-1|| c+p[c]<i ) {
            aux= 0;
        } else {
            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= 0;
    for ( int i= 1; i<n; i+= 2 ) {
        sol+= p[i];
    }
    fout<<sol<<"\n";

    return 0;
}