Cod sursa(job #1021868)

Utilizator xxxcnmvxxxnume cpmplet xxxcnmvxxx Data 4 noiembrie 2013 12:54:41
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MAXN = 1000010;

char S[MAXN];
int X[2 * MAXN];
int Best[MAXN * 2];

int main()
{
    int N, i, st, dr, right = -1, r, center = -1;
    long long Ans = 0;

    in >> (S + 1);
    N = strlen (S + 1);
    for (i = 1; i <= N; i ++)
        X[2 * i] = S[i] - 'a' + 1;
    N = 2 * N + 1;
    X[0] = -1;
    X[N + 1] = -2;

    for (i = 1; i <= N; i ++){
        st = dr = i;

        if (i > right)
            Best[i] = 0;
        else{
            r = i - center;
            Best[i] = Best[center - r];
            if (Best[i] > right - i)
                Best[i] = right - i;

            st -= Best[i];
            dr += Best[i];
        }

        while (X[st - 1] == X[dr + 1])
            Best[i] ++, st --, dr ++;

        if (dr > right)
            right = dr, center = i;

        Ans += (Best[i] + 1) / 2;
    }

    cout << Ans;

    /*int Max = 0, poz;
    for (i = 1; i <= N; i ++)
        if (Best[i] > Max)
            Max = Best[i], poz = i;

    for (i = poz - Max; i <= poz + Max; i ++)
        if (X[i])
            cout << (char) (X[i] + 'a' - 1);*/

    return 0;
}