Cod sursa(job #1311820)

Utilizator gedicaAlpaca Gedit gedica Data 8 ianuarie 2015 16:58:52
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

const int NMAX= 1000000;

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

string s, v;

int d[NMAX*2+2], c;

int main(  )
{
    in >> s;
    int N= s.size();

    for ( int i= 0; i<N; ++i )
    {
        v+= '$';
        v+= s[i];
    }
    v+= '$';

    N= v.size();

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

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

        d[i]= aux;

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

    long long ans= N/2;

    for ( int i= 0; i<N; ++i )
    {
        ans+= d[i]/2;
    }

    out << ans << '\n';

    return 0;
}