hash.cpp (reversed)

Bài viết đang được chỉnh sửa.

#include <stdio.h>

#include <string.h>

#define SMALL 259

#define BIG 1000012309

#define long long long

struct modulo {

    long x;

    void ensure() {

        x = x % BIG;

        while (x < 0) x += BIG;

        while (x >= BIG) x -= BIG;

    }

    modulo(long X) {

        x = X;

        ensure();

    }

    modulo() {

        x = 0;

        ensure();

    }

    modulo operator*(modulo a) { return modulo(a.x * x); }

    modulo operator+(modulo a) { return modulo(a.x + x); }

    modulo operator-(modulo a) { return modulo(a.x - x); }

    bool operator==(modulo a) { return x == a.x; }

};

modulo H[230997];  // one-based

modulo R[230997];

modulo pow_small[230997];

int npow = 0;

void ensure_pow(int n) {

    pow_small[0] = 1;

    while (npow < n) {

        pow_small[npow + 1] = pow_small[npow] * SMALL;

        npow++;

    }

}

void hash(char a[]) {

    int n = strlen(a + 1);

    H[0] = 0;

    R[n + 1] = 0;

    ensure_pow(n);

    for (int i = 1; i <= n; i++) H[i] = H[i - 1] * SMALL + a[i];

    for (int i = n; i >= 1; i--) R[i] = R[i + 1] * SMALL + a[i];

}

modulo hash(int p, int q) {

    if (p < q)

        return H[q] - H[p - 1] * pow_small[q - p + 1];

    else

        return R[q] - R[p + 1] * pow_small[p - q + 1];

}

char a[230997];

int ans[230997];

int n;

int main() {

    scanf("%d%s", &n, a + 1);

    hash(a);

    for (int i = 1; i <= n; i++) {

        int ll, rr, j;

        ll = 1, rr = i, j = (ll + rr) / 2;

        while (ll != j && j != rr) {

            if (hash(1, j) == hash(i, i - j + 1))

                ll = j;

            else

                rr = j;

            j = (ll + rr) / 2;

        }

        for (j = ll; j <= rr; j++)

            if (hash(1, j) == hash(i, i - j + 1))

                ans[i] = j;

    }

    for (int i = 1; i <= n; i++) printf(i == n ? "%d\n" : "%d ", ans[i]);

}