AC 自动机简记

ACAM 初始时为所有模式串构成的一棵 Trie，上面的每个节点对应一个状态，可以视作某个或某些模式串的前缀字符串。根节点可以视为空串。

ACAM 中一个状态 \(u\) 的 fail 指针指向另一个存在于 ACAM 中的状态 \(v=f(u)\)，它是 \(u\) 的最长后缀。

设已经构建好了所有深度小于 \(u\) 的 fail 指针，现在要构建 \(u\) 的 fail 指针。

记 \(F(x,k)\) 表示 \(x\) 的儿子中，状态 \(x\) 末尾连接字符 \(k\) 后的状态。

设 \(F(p,c)=u\)。若 \(F(f(p),c)\) 存在，显然 \(f(u)=F(f(p),c)\)。否则，令 \(p\gets f(p)\)，重复操作。

于是 ACAM 就建好了。

实际建立时，更常见的写法是在 BFS 时使 \(F(p,c)\) 不存在时被赋值为 \(F(f(p),c)\)，这样可以理解为这个不存在的字符串的后缀。在计算 \(u\) 的 fail 指针时就可以直接 \(f(u)\gets F(f(p),c)\)，相当于路径压缩。

匹配时，假装是在 Trie 里面找字符串，如果 fail 了就跳 fail（由于路径压缩，具体实现时不需要特意跳 fail）。目前的点 \(u\) 肯定是已经塞进的字符串的后缀。为了得到所有的匹配，每到一个点就暴力跳一遍 fail，跳过的点标记一下，就能保证时间复杂度。如果要统计更多数据，可以利用 fail 指针与所连接的点构成了一棵树的性质。

因为在前两个模板中我的表现十分愚蠢，所以我只放第三个模板也就是 P5357 的代码。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
int n,t[N][26],f[N],cnt[N],p[N],tot;
vector<int>e[N];
void construct(){
	for(int i=1;i<=n;i++){
		string s;cin>>s;int u=0;
		for(int c:s){
			c-='a';u=(t[u][c]?t[u][c]:t[u][c]=++tot);
		}
		p[i]=u;
	}
	queue<int>q;for(int u:t[0])if(u)q.push(u);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<26;i++){
			if(t[u][i])f[t[u][i]]=t[f[u]][i],q.push(t[u][i]);
			else t[u][i]=t[f[u]][i];
		}
	}
	for(int i=1;i<=tot;i++)e[f[i]].push_back(i);
}
void match(){
	string s;cin>>s;int u=0;
	for(int c:s){
		c-='a';u=t[u][c];cnt[u]++;
	}
}
void dfs(int u){
	for(int v:e[u])dfs(v),cnt[u]+=cnt[v];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;construct();match();dfs(0);
	for(int i=1;i<=n;i++)printf("%d\n",cnt[p[i]]);
	return 0;
}