Cod sursa(job #638907)

Utilizator cont_de_testeCont Teste cont_de_teste Data 21 noiembrie 2011 21:13:20
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
# include <cstdio>
# include <cstring>

const char *FIN = "pscpld.in", *FOU = "pscpld.out";
const int NAX = 1000005;

int V[NAX];
char S[NAX];

inline int min (int a, int b) {
    return a < b ? a : b;
}

inline int calc (int N) {
    return N - 1;
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%s", S + 1);
    int N = strlen (S + 1);

    int st = 1, dr = 1, sol = N;
    for (int j = 2; j <= N; ++j)
        if (j <= dr) {
            V[j] = min (V[st + dr - j], dr - j);
            if (j + V[j] == dr)
                for (st = j - V[j], dr = j + V[j]; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
                    V[j] += 1;
        } else {
            for (st = dr = j; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
                V[j] += 1;
        }
    for (int i = 1; i <= N; ++i)
        sol += calc (V[i] * 2 + 1);
    fprintf (fopen (FOU, "w"), "%d", sol);
}