Cod sursa(job #638925)

Utilizator SpiderManSimoiu Robert SpiderMan Data 21 noiembrie 2011 22:01:09
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
# include <cstdio>
# include <cstring>

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

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

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

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

    int st = 1, dr = 1;
    long long sol = 0;
    for (int j = 1; j <= N; sol += V[j++] + 1)
        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;
        }
    st = 1, dr = 2;
    for (int j = 1; j < N; ++j) {
        if (S[j] == S[j + 1]) {
            if (j <= dr) {
                V[j] = min (V[st + dr - j - 1], dr - j - 1);
                for (st = j - V[j], dr = j + V[j] + 1; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
                    V[j] += 1;
            } else {
                for (dr = (st = j) + 1; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
                    V[j] += 1;
            }
            sol += V[j] + 1;
        } else V[j] = 0;
    }
    fprintf (fopen (FOU, "w"), "%lld", sol);
}