Cod sursa(job #997067)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 13 septembrie 2013 11:46:31
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int Nmax = 1000005;

int N;
char s[Nmax], sir[2 * Nmax];
int P[2 * Nmax];

void read()
{
    ifstream f("pscpld.in");

    f.getline( s, Nmax );

    sir[ ++N ] = '#';

    for ( int i = 0; s[i] != '\0'; ++i )
    {
        sir[ ++N ] = s[i];
        sir[ ++N ] = '#';
    }

    f.close();
}

void Manacher()
{
    ofstream g("pscpld.out");

    int mx = 0, ind = 0, sol = 0;

    for ( int i = 1; i <= N; ++i )
    {
        if ( mx >= i )
        {
            P[i] = min( mx - i, P[2 * ind - 1] );
        }

        while ( i - P[i] >= 1 && i + P[i] < N && sir[i - P[i]-1] == sir[i + P[i] + 1] )
                P[i]++;

        if ( i + P[i] > mx )
        {
            mx = i + P[i];
            ind = i;
        }
    }

    for ( int i = 1; i <= N; ++i )
            sol += ( P[i] + 1 ) / 2;

    g<<sol;
}

int main()
{
    read();
    Manacher();

    return 0;
}