Cod sursa(job #1510590)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 25 octombrie 2015 12:53:26
Problema PScPld Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int Nmax = 1000000;

char S[Nmax];
char s[2 * Nmax + 2];
int Z[Nmax];

int main(void) {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    int n, i;
    int l, r;
    long long answer;

    gets(S);
    fclose(stdin);

    i = 0;
    while (S[i] != '\0') {
        s[2 * i] = '$';
        s[2 * i + 1] = S[i];
        i++;
    }
    s[2 * i] = '$';
    n = 2 * i + 1;
    l = r = 0;
    answer = 0LL;
    for (i = 1; i < n; i++) {
        if (i <= r) {
            Z[i] = min(Z[2 * l - i], r - i);
        }
        while (i - Z[i] - 1 >= 0 && i + Z[i] + 1 < n
                        && s[i - Z[i] - 1] == s[i + Z[i] + 1]) {
            Z[i]++;
        }
        if (i + Z[i] > r) {
            r = i + Z[i];
            l = i;
        }
        answer += (Z[i] + 1) / 2LL;
    }
    printf("%lld\n", answer);
    return 0;
}