Cod sursa(job #973257)

Utilizator Theorytheo .c Theory Data 13 iulie 2013 20:14:25
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int Nmax = 1000005;

int N; char S[Nmax]; int Sol[2 * Nmax]; int X[2 * Nmax];

void Read() {

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

void Solve() {

    int Center = -10000; int Right = -10000;

    for(int i = 1; i <= N; ++i) {
        int St = i, Dr = i;

        if(i >  Right)
            Sol[i] = 0;
        else {
            int Radius = Right - Center;
            Sol[i] = Sol[Center - Radius];
            if(Sol[i] + i > Right)
                Sol[i] = Right - i;
            St = St - Sol[i]; Dr += Sol[i];
        }
        while(X[St - 1] == X[Dr + 1])
            St--, ++Dr, ++Sol[i];
        if(Dr > Right)
            Right = Dr, Center = i;
    }
}

int main() {

    Read();

    Solve();
    long long Solution = 0;

    for(int i = 1; i <= N; ++i)
        Solution += (Sol[i] + 1) / 2;

    fout << Solution <<'\n';
    return 0;
}