【复制】题解：AT_abc362_g [ABC362G] Count Substring Query / AC 自动机学习笔记
ivyjiao
·
·
算法·理论
原稿：https://www.luogu.com.cn/article/uxz00lnh
前置知识：
-
P8306 【模板】字典树
-
B3644 【模板】拓扑排序 / 家谱树
-
什么是 AC 自动机？
AC 自动机，又称自动 AC 机，全称 Aho-Corasick automaton。
- 构造一棵 Trie 树。
- 构造 Fail 指针。
- 匹配。
这是你的前置知识，在此不做讲解。
代码：
void insert(string s,int now){
int u=0;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
if(!trie[u][c]) trie[u][c]=++cnt;
u=trie[u][c];
}
if(!vis[u]) vis[u]=now;//记录每个字符串都在哪个位置。
//因为可能有重复的字符串，所以把所有相同的字符串指向第一次出现的位置。
rev[now]=vis[u];//反向的vis，方便最后输出。
}
Fail 指针指向 Trie 树中该路径的最长后缀。
如图，红色指针即为一些 Fail 指针，b_ 和 _a 就是 b 和 a。
在本文我们不把 Fail 指针与 Kmp 数组作比较。
设当前节点为 u，trie[f][c]=u。
设深度小于 u 的所有结点的 Fail 指针都已求得。
- 如果 trie[fail[f]][c] 存在，则 fail[trie[f][c]]=trie[fail[f]][c]。
证明：因为 fail[f] 是 f 的后缀，所以 trie[fail[f]][c] 是 trie[f][c]，即 u 的后缀。
- 如果 trie[fail[f]][c] 不存在，那么我们继续找到 trie[fail[fail[f]]][c]。重复 1 的判断过程，一直跳 Fail 指针直到根结点。
证明：因为 fail[f] 是 f 的后缀，fail[fail[f]]
是 fail[f] 的后缀，所以 fail[fail[f]] 是 f 的后缀，所以 trie[fail[fail[f]]][c] 是 trie[f][c]，即 u 的后缀。
- 如果跳到最后都没有，指向根节点。
代码细节：
- 求 Fail 要用 BFS。
证明：由于我们假设深度小于 u 的所有结点的 Fail 指针都已求得，跳 Fail 时节点深度也只会越来越小，所以求 Fail 要用 BFS。
- 若 u，即 trie[f][c] 不存在，令 trie[f][c]=trie[fail[f]][c]。
证明：因为 fail[f] 是 f 的后缀，所以 trie[fail[f]][c] 是 trie[f][c] 的后缀。由于我们 trie[f][c] 路径肯定比 trie[fail[f]][c] 路径要长，匹配了 trie[f][c] 路径一定能匹配 trie[fail[f]][c] 路径，所以不会影响答案。
好处：直接记录下一个能匹配的位置，压缩了跳 Fail 的路径，把 O(\log n) 的复杂度压缩到 O(1)，不会被卡掉。
当然，如果 trie[fail[f]][c] 也不存在，那就无事发生了（即连回根节点）。
这个东西也是可以自指的。
代码：
void getfail(){
queue<int>q;
for(int i=0;i<26;i++){
if(trie[0][i]) q.push(trie[0][i]);
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(trie[u][i]){
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
ins[trie[fail[u]][i]]++;//为后面的拓扑排序做准备。
}
else trie[u][i]=trie[fail[u]][i];//路径压缩。
}
}
}
```cpp
void query(string t){
int u=0;
for(int i=0;i<t.size();i++){
u=trie[u][t[i]-'a'];//此时的trie树已经被修改了，该步骤一定成立。
for(int j=u;j;j=fail[j]) ans[vis[j]]++;
}
}
```
我们也可以只标记找到的节点，再用拓扑排序求出答案。
此部分代码需要结合拓扑排序部分代码理解。
代码：
```cpp
void query(string t){
int u=0;
for(int i=0;i<t.size();i++){
u=trie[u][t[i]-'a'];//此时的trie树已经被修改了，该步骤一定成立。
ans[u]++;
}
}
```
- Fail 树
又称失配树。
所有的 Fail 边构成一棵树。
证明：
1. Fail 边不会成环。
2. Fail 边的深度比当前节点的深度要小。
- 拓扑排序优化
由于所有的 Fail 边构成一棵树，所以可以对其进行拓扑排序，从而求得答案。
```cpp
void topu(){
queue<int>q;
for(int i=1;i<=cnt;i++){
if(!ins[i]) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
flag[vis[u]]=ans[u];
//统计每个字符串出现的次数，若vis[u]=0则代表该位置不是字符串的结尾。
int v=fail[u];//遍历失配树。
ans[v]+=ans[u];//下传答案。
//能够这样做的原因是：如果一个字符串出现了n次，那么它的后缀也会出现至少n次。
if(!(--ins[v])) q.push(v);//拓扑排序流程
}
}
```
到这里我们的答案就求出来了。
- 输出答案
很显然，输出 $flag[rev[i]]$。
```cpp
for(int i=1;i<=n;i++) cout<<flag[rev[i]]<<endl;
```
- 完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,trie[5000001][27],fail[5000001],flag[5000001],rev[5000001],cnt,vis[5000001],ins[5000001],l,maxn,ans[500001];
string s[500001],t;
void insert(string s,int now){
int u=0;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
if(!trie[u][c]) trie[u][c]=++cnt;
u=trie[u][c];
}
if(!vis[u]) vis[u]=now;
rev[now]=vis[u];
}
void getfail(){
queue<int>q;
for(int i=0;i<26;i++){
if(trie[0][i]) q.push(trie[0][i]);
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(trie[u][i]){
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
ins[trie[fail[u]][i]]++;
}
else trie[u][i]=trie[fail[u]][i];
}
}
}
void query(string t){
int u=0;
for(int i=0;i<t.size();i++){
u=trie[u][t[i]-'a'];
ans[u]++;
}
}
void topu(){
queue<int>q;
for(int i=1;i<=cnt;i++){
if(!ins[i]) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
flag[vis[u]]=ans[u];
int v=fail[u];
ans[v]+=ans[u];
if(!(--ins[v])) q.push(v);
}
}
int main(){
cin>>t;
while(cin>>n&&n){
memset(trie,0,sizeof trie);
memset(ans,0,sizeof ans);
memset(fail,0,sizeof fail);
memset(vis,0,sizeof vis);
memset(flag,0,sizeof flag);
cnt=0;
l=0;
for(int i=1;i<=n;i++){
cin>>s[i];
insert(s[i],i);
}
getfail();
query(t);
topu();
for(int i=1;i<=n;i++) cout<<flag[rev[i]]<<endl;
}
}
```