Cod sursa(job #1019155)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 30 octombrie 2013 18:52:56
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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;

int po[nmax+1], pe[nmax+1];

int main(  ) {
    fin>>s;
    int n= s.size();

    i64 sol= 0;
    int cp= -1;
    for ( int i= 0; i<n; ++i ) {
        int aux;
        if ( cp==-1|| cp+po[cp]<i ) {
            aux= 0;
        } else {
            aux= min(po[2*cp-i], cp+po[cp]-i);
        }

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

        po[i]= aux;
        if ( cp+po[cp]<i+po[i] ) {
            cp= i;
        }
        sol+= po[i]+1;
    }

    cp= 0;
    for ( int i= 1; i<n; ++i ) {
        if ( s[i-1]==s[i] ) {
            int aux;
            if ( cp+pe[cp]-1<i ) {
                aux= 1;
            } else {
                aux= min(pe[2*cp-i], cp+pe[cp]-1-i);
            }
            
            while ( i-aux-1>=0&& i+aux<n&& s[i-aux-1]==s[i+aux] ) {
                ++aux;
            }

            pe[i]= aux;
            if ( cp+pe[cp]-1<i+pe[i]-1 ) {
                cp= i;
            }
            sol+= pe[i];
        }
    }

    fout<<sol<<"\n";

    return 0;
}