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]);
}