Cod sursa(job #1621634)

Utilizator algebristulFilip Berila algebristul Data 29 februarie 2016 20:25:46
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int nmax = 1000007;
int n;
int d[nmax * 2];
char s[nmax * 2];
char w[nmax];

long long manacher() {
    long long ans = 0;

    for (int i = 1, j = 0; i <= n; i++) {
        s[++j] = w[i];
        s[++j] = '#';
    }

    n = 2*n;

    int l = 0, r = 0, c = 0;

    for (int i = 1; i <= n; i++) {
        if (i <= r) {
            int j = 2 * c - i;

            if (j - d[j] > l) {
                d[i] = d[j];
            } else {
                d[i] = j - l;
            }
        } else {
            d[i] = 0;
        }

        while (i + d[i] <= n && i - d[i] >= 1) {
            if (s[i + d[i]] != s[i - d[i]])
                break;
            d[i]++;
        }

        if (i + d[i] > r) {
            c = i;
            r = i + d[i];
            l = i - d[i];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (s[i] == '#')
            ans += d[i]/2;
        else
            ans += (d[i] + 1)/2;
    }

    return ans;
}

int main() {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    
    scanf("%s", w + 1);
    n = strlen(w + 1);

    printf("%lld\n", manacher());

    return 0;
}