更新日志
2025/01/23：开工。
概念
首先，你应该会KMP算法。
AC自动机，本质上就是利用 KMP 的思想同时对多个模式串进行匹配。
具体的，我们将建立一棵 Trie，并在 Trie 上开展匹配。
思路
预处理（建Trie）
前面已经说过，我们将在 Trie 上开展匹配，所以首先我们将建一棵 Trie。
只要常规地把所有匹配串加入即可，记得记录每个匹配串对应的节点编号以统计答案。
失配处理（fail）
首先我们明确，一个节点表示一个状态，也就是说，如果我们当前位于 \(u\) 节点，那么当前状态就是 \(root\rightarrow u\) 的路径，表示这一条路径上的字符已经匹配完成。
\(fail\) 的概念与 KMP 中 border 重心概念下 \(nxt\) 的概念很接近，形式化的，\(fail_u\) 储存了 \(u\) 的存在的最长后缀状态。比如当前 Trie 中已有 \(\texttt{abcde}\) 和 \(\texttt{bcde}\) 和 \(\texttt{cde}\)，那么 \(fail_{\texttt{abcde}}=\texttt{bcde}\)。
下面我们考虑如何得到 \(fail\)，假如当前位于 \(u\)，\(v=\mathrm{Trie}(u,\texttt{c})\)，且 \(fail_u,\mathrm{Trie}(fail_u,\texttt{c})\) 已知，，那么：
\[fail_v\gets \mathrm{Trie}(fail_u,\texttt{c}) \]但这是很片面的，我们需要考虑更全面的情况。
比如说，如果 \(\mathrm{Trie}(fail_u,\texttt{c})\) 不存在，那么显然：
\[fail_v\gets \mathrm{Trie}(fail_{fail_u},\texttt{c}) \]直到至 \(root\) 仍不存在 \(\mathrm{Trie}(root,\texttt{c})\)，那么：
\[fail_v\gets root \]不难发现一个较为显然的优化，我们可以考虑路径压缩。
考虑如何保证 \(fail_u,\mathrm{Trie}(fail_u,\texttt{c})\)，我们只需要 BFS 更新即可。因为 \(fail_u\) 的深度必然小于 \(u\) 的。
匹配
令进行匹配的字符串为 \(s\)。
从 Trie 的根节点开始，向下逐位匹配，如果当前状态存在对应的下一个状态，那么直接跳至对应状态即可，并更新对应状态的匹配答案数。
如果当前状态没有相应的下一个状态，那我们就跳 \(fail\)，直到找到一个可以匹配的状态或者回到 \(root\)（匹配不上）为止。
不难发现，路径压缩同时可以优化匹配过程。
值得注意的是，在当前位置更新答案后，当前状态的所有后缀状态都要跟着更新，也就是一路跳 \(fail\) 至根节点路径上每个状态都得更新。
优化
路径压缩
在实现部分已经提到，那么如何具体实现呢？
我们更新 \(nxt_{u,\texttt{c}}\) 的定义，不再是 \(\mathrm{Trie}(u,\texttt{c})\)，而是当前状态后面再加上 \(\texttt{c}\) 可以转移到的下一个匹配状态。
更具体的，如果存在 \(\mathrm{Trie}(u,\texttt{c})\)，那么 \(nxt_{u,\texttt{c}}\gets \mathrm{Trie}(u,\texttt{c})\)。否则，\(nxt_{u,\texttt{c}}\gets nxt_{fail_u,\texttt{c}}\)。（\(nxt_{fail_u,\texttt{c}}\) 已经优先处理过了）
特殊的，若 \(nxt_{root,\texttt{c}}\) 不存在，\(nxt_{root,\texttt{c}}\gets root\)。
DFS优化
我们考虑优化更新当前状态的所有后缀状态的过程。
不难想到，我们可以先统计出每个点各自的答案，然后按顺序一路传递。
具体的，我们对于每一组 \(fail\)，在图上从 \(fail_u\) 连向 \(u\)，匹配完后 DFS 这个图，对当前节点的每一个子节点，都对其进行 DFS，并更新当前点答案。
由于每个点只有一个 \(fail\)，所以每个点只会被遍历一次，复杂度是 \(O(n)\) 的。
模板
struct ac_automaton{
struct node{
int nxt[26];
int ans,fail;
void clear(){
memset(nxt,0,sizeof(nxt));
ans=fail=0;
}
}ns[L];
int tot;
vec<int> g[L];
int insert(string s){
int now=0;
repl(i,0,s.size()){
int &nxt=ns[now].nxt[s[i]-'a'];
if(!nxt)nxt=++tot,ns[nxt].clear();
now=nxt;
}
return now;
}
void build(){
queue<int> q;
repl(i,0,26)if(ns[0].nxt[i]){
q.push(ns[0].nxt[i]);
g[0].pub(ns[0].nxt[i]);
}
while(!q.empty()){
int now=q.front();q.pop();
repl(i,0,26){
if(ns[now].nxt[i]){
ns[ns[now].nxt[i]].fail=ns[ns[now].fail].nxt[i];
g[ns[ns[now].fail].nxt[i]].pub(ns[now].nxt[i]);
q.push(ns[now].nxt[i]);
}else ns[now].nxt[i]=ns[ns[now].fail].nxt[i];
}
}
}
void dfs(int now){
for(int nxt:g[now]){
dfs(nxt);
ns[now].ans+=ns[nxt].ans;
}
}
void query(string s){
int now=0;
repl(i,0,s.size()){
now=ns[now].nxt[s[i]-'a'];
ns[now].ans++;
}
dfs(0);
}
};
例题
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const int L=2e5+5;
struct ac_automaton{
struct node{
int nxt[26];
int ans,fail;
void clear(){
memset(nxt,0,sizeof(nxt));
ans=fail=0;
}
}ns[L];
int tot;
vec<int> g[L];
int insert(string s){
int now=0;
repl(i,0,s.size()){
int &nxt=ns[now].nxt[s[i]-'a'];
if(!nxt)nxt=++tot,ns[nxt].clear();
now=nxt;
}
return now;
}
void build(){
queue<int> q;
repl(i,0,26)if(ns[0].nxt[i]){
q.push(ns[0].nxt[i]);
g[0].pub(ns[0].nxt[i]);
}
while(!q.empty()){
int now=q.front();q.pop();
repl(i,0,26){
if(ns[now].nxt[i]){
ns[ns[now].nxt[i]].fail=ns[ns[now].fail].nxt[i];
g[ns[ns[now].fail].nxt[i]].pub(ns[now].nxt[i]);
q.push(ns[now].nxt[i]);
}else ns[now].nxt[i]=ns[ns[now].fail].nxt[i];
}
}
}
void dfs(int now){
for(int nxt:g[now]){
dfs(nxt);
ns[now].ans+=ns[nxt].ans;
}
}
void query(string s){
int now=0;
repl(i,0,s.size()){
now=ns[now].nxt[s[i]-'a'];
ns[now].ans++;
}
dfs(0);
}
}aca;
const int N=2e5+5;
int n;
string s,t;
int id[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
rep(i,1,n)cin>>t,id[i]=aca.insert(t);
aca.build();
cin>>s;
aca.query(s);
rep(i,1,n)cout<<aca.ns[id[i]].ans<<"\n";
return 0;
}