1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (100000 + 5)
#define INF (0X7FFFFFFF)
#define MAXZ (26)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct xds {
struct node {
int le, ri, zh;
} b[MAXN << 2];
void js(int dq, int le, int ri) {
b[dq].zh = INF, b[dq].le = le, b[dq].ri = ri;
if (le == ri) return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
int cx(int dq, int wz) {
int re = b[dq].zh;
if (b[dq].le == b[dq].ri) return re;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi) return min(cx(LS(dq), wz), re);
else return min(cx(RS(dq), wz), re);
}
void xg(int dq, int le, int ri, int zh) {
if (le > ri) return ;
if (b[dq].le == le && b[dq].ri == ri) {
b[dq].zh = min(b[dq].zh, zh);
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi) xg(LS(dq), le, ri, zh);
else if (le > mi) xg(RS(dq), le, ri, zh);
else xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
}
};
struct SAM {
struct node {
int maxlen, suff_link, trans[MAXZ], size, wz;
node (int maxlen = 0): maxlen(maxlen), suff_link(0), size(0) { memset(trans, 0, sizeof(trans)); }
} b[MAXN << 1];
struct edg {
int to, next;
} tb[MAXN << 1];
int s, last, cntb, g[MAXN << 1], cntt, n;
xds qwq, qaq;
void init() { s = last = cntb = 1, n = 0; }
void adn(int from, int to) {
tb[++cntt].next = g[from];
tb[cntt].to = to;
g[from] = cntt;
}
void ins(char xc) {
int y = xc - 'a', dq = ++cntb, dql = last;
b[dq] = node(b[dql].maxlen + 1);
for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link) b[dql].trans[y] = dq;
if (!dql) b[dq].suff_link = s;
else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen) b[dq].suff_link = b[dql].trans[y];
else {
int c = ++cntb, dqd = b[dql].trans[y];
b[c] = node(b[dql].maxlen + 1);
b[c].suff_link = b[dqd].suff_link;
b[dq].suff_link = b[dqd].suff_link = c;
for (int i = 0; i < MAXZ; i++) b[c].trans[i] = b[dqd].trans[i];
for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link) b[dql].trans[y] = c;
}
b[dq].wz = ++n;
b[last = dq].size = 1;
}
int dfs(int dq) {
for (int i = g[dq]; i; i = tb[i].next) b[dq].size += dfs(tb[i].to);
return b[dq].size;
}
void solve() {
for (int i = 2; i <= cntb; i++) adn(b[i].suff_link, i);
dfs(1);
qwq.js(1, 1, n), qaq.js(1, 1, n);
for (int i = 1; i <= cntb; i++)
if (b[i].size == 1) {
qaq.xg(1, 1, b[i].wz - b[b[i].suff_link].maxlen, b[i].maxlen + 1);
qwq.xg(1, b[i].wz - b[b[i].suff_link].maxlen + 1, b[i].wz, b[b[i].suff_link].maxlen + 1);
}
for (int i = 1; i <= n; i++)
printf("%d\n", min(qwq.cx(1, i), qaq.cx(1, i) - i));
}
} refun;
int n;
char s[MAXN];
int main() {
scanf("%s", s);
n = strlen(s);
refun.init();
for (int i = 0; i < n; i++)
refun.ins(s[i]);
refun.solve();
return 0;
}
|