Cod sursa(job #1227525)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 10 septembrie 2014 19:39:50
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb

using namespace std;

#include <fstream>
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

string s;
int DIM[2][100001];

long long SOL;

int main ()
{

    ifstream in ("pscpld.in");
    freopen("pscpld.out","w",stdout);

    in>>s;

    int position1=0,position2=0;

    for ( int i=1 ; i <= s.size() ; ++i )
    {

        DIM[0][i]=0;
        if ( position1 + DIM[0][position1] >= i )
            DIM[0][i]=max(DIM[0][i],min(DIM[0][2*position1-i],position1+DIM[0][position1]-i));
        for ( ; i-DIM[0][i]-1 >= 1 && i+DIM[0][i]+1 <= s.size() && s[i-DIM[0][i]-2] == s[i+DIM[0][i]] ; ++DIM[0][i]);
        if ( i+DIM[0][i] > position1+DIM[0][position1] )
            position1=i;
        ++SOL;
        SOL+=DIM[0][i];
        DIM[1][i]=0;
        if ( position2+DIM[1][position2] >= i+1 )
             DIM[1][i]=max(DIM[1][i],min(DIM[1][2*position2-i],position2+DIM[1][position2]-i));
        for ( ; i-DIM[1][i] >= 1 && i+DIM[1][i]+1 <= s.size() && s[i-DIM[1][i]-1] == s[i+DIM[1][i]] ; ++DIM[1][i]);
        if ( i+DIM[1][i] > position2+DIM[1][position2] )
            position2=i;
        SOL+=DIM[1][i];

    }

    printf("%lld",SOL);
    return 0;

}