Cod sursa(job #1510503)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 25 octombrie 2015 09:41:32
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstring>

typedef unsigned long long ull;

const int Nmax = 1000000;
const int BASE = 97;

char s[Nmax + 1];
char S[2 * Nmax + 2];
ull H[2 * Nmax + 2], h[2 * Nmax + 2];
ull pow[2 * Nmax + 2];

int n;

inline ull GetHash(int position, int siz) {
    return H[position + siz - 1] - (position ? H[position - 1] * pow[siz] : 0ULL);
}

inline ull GetHashBackwards(int position, int siz) {
    return h[position] - (position + siz < n ? h[position + siz] * pow[siz] : 0ULL);
}

int main(void) {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    int i, lo, hi, mid;
    long long r;

    // citire
    gets(s);
    fclose(stdin);

    r = strlen(s);
    S[0] = '$';
    for (i = 0; i < r; i++) {
        S[2 * i + 1] = s[i];
        S[2 * i + 2] = '$';
    }
    n = 2 * r + 2;

    // precalculare puteri
    pow[0] = 1ULL;
    for (i = 1; i < n; i++) {
        pow[i] = pow[i - 1] * BASE;
    }
    // precalculare hash
    H[0] = S[0];
    for (i = 1; i < n; i++) {
        H[i] = H[i - 1] * BASE + S[i];
    }
    // precalculare hash pe invers
    h[n - 1] = S[n - 1];
    for (i = n - 2; i >= 0; i--) {
        h[i] = h[i + 1] * BASE + S[i];
    }

    r = 0LL;
    for (i = 1; i < n; i++) {
        lo = 0;
        hi = i + 1;
        while (hi - lo > 1) {
            mid = (lo + hi) / 2;
            if (GetHash(i - mid, mid) == GetHashBackwards(i + 1, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        r += (lo + 1) / 2;
        // printf("Reporting %d %d\n", i + 1, lo);
    }
    printf("%lld\n", r);
    return 0;
}