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
| const int N = 100010, M = N * 2;
int n;
char str[N];
struct SAM {
int maxlen[M], trans[M][26], link[M], sz, last;
SAM() { sz = last = 1; }
void init() {
memset(maxlen, 0, sizeof maxlen);
memset(trans, 0, sizeof trans);
memset(link, 0, sizeof link);
sz = last = 1;
}
void extend(int ch) {
int cur = ++sz, p = last;
maxlen[cur] = maxlen[p] + 1;
cnt[cur] = 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++sz;
maxlen[clone] = maxlen[p] + 1;
memcpy(trans[clone], trans[q], sizeof trans[clone]);
link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
} sam;
for (int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
for(int i = 1; i <= sam.sz; i++) a[sam.maxlen[i]]++;
for(int i = 1; i <= sam.sz; i++) a[i] += a[i - 1];
for(int i = 1; i <= sam.sz; i++) b[a[sam.maxlen[i]]--] = i;
|