广义后缀自动机，即多串的 SAM。
推荐 辰星凌的博客。
设 trie 树大小 \(|T|\)，字符集大小 \(|A|\)；
设 \(G(T)\) 表示 \(T\) 的所有叶子深度之和。
在线做法
每次插入新串时，将 \(last\) 重置，并加入特判。
复杂度 \(\mathcal O(|T||A|+G(T))\)，常数比离线做法小。
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
| struct SuffixAutomaton {
int tot;
int ch[N][26], link[N], len[N], pos[N];
SuffixAutomaton() : tot(1) {}
inline int insert(int c, int last) {
if (ch[last][c]) {
int p = last, q = ch[p][c];
if (len[q] == len[p] + 1) return q;
else {
int nq = ++tot;
len[nq] = len[p] + 1, link[nq] = link[q];
memcpy(ch[nq], ch[q], sizeof ch[q]);
link[q] = nq;
while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
return nq;
}
}
int p = last, np = ++tot;
len[np] = len[p] + 1;
while (p && !ch[p][c]) ch[p][c] = np, p = link[p];
if (!p) link[np] = 1;
else {
int q = ch[p][c];
if (len[q] == len[p] + 1) link[np] = q;
else {
int nq = ++tot;
len[nq] = len[p] + 1, link[nq] = link[q];
memcpy(ch[nq], ch[q], sizeof ch[q]);
link[q] = link[np] = nq;
while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
}
}
return np;
}
} A;
|
离线做法
先将所有串插到 trie 里，再 bfs 构建。
复杂度 \(\mathcal O(|T||A|+|T|)\)。
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
| struct Trie {
int tot;
int ch[N][26], fa[N], val[N];
Trie() : tot(1) {}
inline void insert(char *s) {
int p = 1;
for (int i = 0; s[i]; ++i) {
int c = s[i] - 'a';
if (!ch[p][c]) {
ch[p][c] = ++tot;
val[ch[p][c]] = c, fa[ch[p][c]] = p;
}
p = ch[p][c];
}
}
} T;
struct SuffixAutomaton {
int tot;
int ch[N][26], link[N], len[N], pos[N];
queue<int> q;
SuffixAutomaton() : tot(1) {}
inline int insert(int c, int last) {
int p = last, np = ++tot;
len[np] = len[p] + 1;
while (p && !ch[p][c]) ch[p][c] = np, p = link[p];
if (!p) link[np] = 1;
else {
int q = ch[p][c];
if (len[q] == len[p] + 1) link[np] = q;
else {
int nq = ++tot;
len[nq] = len[p] + 1, link[nq] = link[q];
memcpy(ch[nq], ch[q], sizeof ch[q]);
link[q] = link[np] = nq;
while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
}
}
return np;
}
inline void build() {
for (int i = 0; i < 26; ++i)
if (T.ch[1][i]) q.push(T.ch[1][i]);
pos[1] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
pos[u] = insert(T.val[u], pos[T.fa[u]]);
for (int i = 0; i < 26; ++i)
if (T.ch[u][i]) q.push(T.ch[u][i]);
}
}
} A;
|