Cod sursa(job #1345708)

Utilizator PikachuPikachu Pikachu Data 17 februarie 2015 20:26:14
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

const int NMAX = 1000000;

int p[NMAX * 2 + 1];
string v;
char s[NMAX + 5];

void solve(int poz, int n) {
    while(poz - p[poz] >= 0 && poz + p[poz] < n && v[poz - p[poz]] == v[poz + p[poz]])
        ++ p[poz];
    -- p[poz];
}

int main() {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    int n, j = 0, aux, st, dr;
    long long rasp = 0;

    gets(s);
    n = strlen(s);

    for(int i = 0; i < n; ++ i) {
        v = v + "#" + s[i];
    }

    v += "#";

    n = n * 2 + 1;

    for(int i = 0; i < n; ++ i) {
        aux = 2 * j - i;
        st = j - p[j];
        dr = j + p[j];
        if( i > dr ) {
            solve(i, n);
            j = i;
        } else
        if( aux - p[aux] > st ) {
            p[i] = p[aux];
        } else {
            p[i] = dr - i;
            solve(i, n);
            j = i;
        }
    }

    for(int i = 0; i < n; ++ i) {
        rasp += (p[i] + 1) / 2;
        //printf("%d ", p[i]);
    }

    printf("%lld", rasp);

    return 0;
}