AC自动机
前置知识
- 一个讲的很清楚细致的B站阿婆主视频
点击访问
- 几张借用的图片,进行实例的模拟
关键点:father_fail指针。初始化求ne的过程
思想:贪心的思想:利用父节点后缀最长,延伸到子节点后缀最长,是一个bfs的过程。
用到的数组:ne[]表示当前节点的最长后缀对应的前缀结尾节点编号。
含义:当前节点son_id(节点信息是v)的父亲节点t的最长后缀所对应的前缀结尾节点编号。
作用:求得当前节点的最长后缀。
方法与过程:求得fa_fail = ne[t],尝试这个节点是否存在。
(1). 若存在,则这个节点的ne[son_id] = tr[fa_fail][v];
(2). 若不存在,则重复上述过程直至fa_fail到达根节点0,此时退出循环,再从根节点进行特判是否存在v这个信息的子节点tr[fa_fail][v]。
有则:ne[son_id] = tr[fa_fail][v];
无则:ne[son_id] = 0;
解释原因:
根据ne的定义表示的是当前节点的最长后缀对应的前缀结尾节点编号。
而fa_fail那个节点对应的是父节点的最长后缀,
所以若有与v信息相同的子节点,则该子节点就是son_id的最长后缀。
若当前的fa_fail没有与v信息相同的子节点,则保持父节点的后缀信息不变,继续找fa_fail的最长后缀对应的前缀尾结点,
这个点与son_id的父节点的后缀信息(并非最长后缀)相同,所以仍旧是在贪心地尽可能寻找son_id的最长后缀对应的前缀尾结点。
匹配过程
对于整个长串,在Tire树上进行匹配
t表示当前在Tire树上所指的节点,v表示当前遍历到的字母。
(1). 若t有v这个信息的子节点,则跳过去
(2). 若t没有v这个信息的子节点,也不必从根节点进行查找,而是直接去看他的ne[t]即可。
因为首先,若没有找到,则表示从根节点到tr[t][v]这段的单词root~tr[t][v]不存在。
此时可能的单词只有比root~tr[t][v]更短的,即后缀部分。
而ne[t]表示的是t这个点最长后缀对应的前缀,所以可以继续尝试,
直至找到以tr[t][v]这个点结尾的单词或者到达根节点为止。
AC自动机代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int T, n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];
void insert() {
int p = 0;
for (int i = 0; str[i]; ++i) {
int v = str[i] - 'a';
if (!tr[p][v]) tr[p][v] = ++idx;
p = tr[p][v];
}
cnt[p]++;
}
void build() {
int hh = 0, tt = -1;
int root = 0;
for (int i = 0; i < 26; ++i) {
int son_id = tr[root][i];
if (!son_id) continue;
ne[son_id] = root;
q[++tt] = son_id;
}
while (hh <= tt) {
int t = q[hh++];
for (int i = 0; i < 26; ++i) {
int son_id = tr[t][i];
if (!son_id) continue;
int j = ne[t]; // j 即 father_fail
while (j && !tr[j][i]) j = ne[j];
if (tr[j][i]) ne[son_id] = tr[j][i];
else ne[son_id] = root;
q[++tt] = son_id;
}
}
}
int main() {
scanf("%d", &T);
while (T--) {
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%s", str);
insert();
}
build();
scanf("%s", str);
int res = 0;
int t = 0;
for (int i = 0; str[i]; ++i) {
int v = str[i] - 'a';
int son_id = tr[t][v];
if (son_id) {
t = son_id;
res += cnt[t];
cnt[t] = 0;
} else {
while (t && !tr[t][v]) { // 不在使用fa_fail信息,而是使用最长后缀ne的信息
t = ne[t];
res += cnt[t];
cnt[t] = 0;
}
if (tr[t][v]) {
t = tr[t][v];
res += cnt[t];
cnt[t] = 0;
}
}
}
printf("%d\n", res);
}
return 0;
}