Cod sursa(job #973267)

Utilizator Theorytheo .c Theory Data 13 iulie 2013 21:08:50
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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; i <= N; ++i)
        X[2 * i] = S[i] - 'a' + 1;
    N = 2 * N + 1; X[0] = -1; X[N + 1] = -2;
}

void Solve() {

    int Center = -1000; int Right = -1000;

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

        if(i >  Right)
            Sol[i] = 0;
        else {
            int Radius = i - Center;
            Sol[i] = Sol[Center - Radius];
            if(Sol[i] + i > Right)
                Sol[i] = Right - i;
            St = St - Sol[i]; Dr = 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;
}