我会五种自动机:
WA自动机,TLE自动机,RE自动机,CE自动机和UKE自动机,就是不会AC自动机
问题:给出 $M$ 个模式串 $P_i$,问有多少个模式串在字符串 $S$ 中出现过。
P1 = a
P2 = ab
S = abc
暴力算法:每个模式串都建 $next$ 数组,都和 $S$ 匹配一次 $O(M(|S|+|P|))$
每个模式串都使用 $KMP$ 进行匹配的话,太慢了
考虑将模式串都组合在一起,建立 “$next$ 数组”
fail 指针
先将所有模式串建成一颗 $Trie$ 树
$\operatorname{KMP} \ next$ 数组:对于字符串 $P$ 的前 $i$ 个字符构成的子串既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作 next[i]
$\operatorname{fail}$ 指针:每个节点的 $\operatorname{fail}$ 指针指向 $Trie$ 树上该节点所代表字符串的最长后缀节点
使用 $\operatorname{BFS}$ 逐层构建 $\operatorname{fail}$ 指针
代码实现
// 插入 Trie 树
for (int i = 1; i <= n; ++i) {
cin >> s;
int x = 0;
for (int j = 0; s[j]; ++j) {
if (!ch[x][s[j]-'A']) ch[x][s[j]-'A'] = tot++;
x = ch[x][s[j]-'A'];
}
cnt[x] += 1;
}
// BFS 遍历求 next 指针
int s = 0, e = 1;
q[0] = next[0] = 0;
while (s < e) {
int x = q[s++];
for (int j = 0; j < 26; ++j) {
if (ch[x][j]) {
q[e++] = ch[x][j];
next[ch[x]][j] = (!x)?0:ch[next[x]][j];
}
else {
ch[x][j] = ch[next[x]][j];
}
}
}
查询一个串 s 里出现了几次模板串
int x = 0, res = 0;
for (int i = 0; s[i]; ++i) {
res += cnt[x];
x = ch[x][s[i]-'A'];
}
因为 ch[x]
已经把所有的 $26$ 种可能的转移都处理好了。
AKWF自动机和TP自动机了解一下
AKIOI自动机和JC自动机了解一下