Cod sursa(job #1345620)

Utilizator Athena99Anghel Anca Athena99 Data 17 februarie 2015 19:20:37
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <string>

using namespace std;

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

typedef long long i64;

const int nmax= 1000000;

int n, d[2*nmax+5];
string s, a;

int main(  ) {
    fin>>a;
    s.push_back(' '), s.push_back('$'); n= 1;
    for ( int i= 0; i<(int)a.size(); ++i ) {
        s.push_back(a[i]);
        s.push_back('$'); n+= 2;
    }

    for ( int i= 1, right= 0, pos= 0; i<=n; ++i ) {
        if ( i>right ) {
            int j;
            d[i]= 1;
            
            for ( j= 1; s[i-j]==s[i+j]; ++j ) ; --j;
            d[i]+= j, pos= i, right= i+j;

        } else {
            if ( i+d[2*pos-i]-1<right ) {
                d[i]= d[2*pos-i];
            } else {
                int j;
                d[i]= right-i+1;

                for ( j= 1; s[2*i-right-j]==s[right+j]; ++j ) ; --j;
                d[i]+= j, pos= i, right= right+j;
            }
        }
    }

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

    return 0;
}