AC自动机学习笔记

前言 & 介绍

学习AC自动机时，发现很多讲解都比较难以理解（可能是我太菜了）。

通过学习dalao的学习笔记，自主研发和学长的讲解终于贯彻理解了AC自动机（真的贯彻吗）。

所以，我尝试发一篇我认为比较容易理解的讲解。

前置知识：

1. 字典树（trie树）
2. KMP（非必会）

介绍：

AC自动机是一种可以解决多匹配串和单文本串匹配的字符串匹配算法，是一种有限状态自动机，如果你学过KMP，那么理解起来相对轻松，它的理解难度低于KMP算法。

正文：

有限状态自动机：

有限状态自动机是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。
——摘自百度百科

怎么样，理解没？我猜你没理解，那我们用人类语言描述一下吧。

如果你上过初中，那你肯定做过模拟程序运行题，给你一个程序流程图，让你预测它的输出结果，它就是一种简单的自动机模型。

本质上，自动机就是输入一种信号，在它内部经过决策和计算，最终接受答案的数学模型，我们要做到就是实现它内部的决策与计算。

AC自动机：

首先用一道例题引入 :

给定 (n) 个模式串 (s_i) 和一个文本串 (t)，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

• 对于 (50%) 的数据，保证 (n = 1)。
• 对于 (100%) 的数据，保证 (1 leq n leq 10^6)，(1 leq |t| leq 10^6)，(1 leq sumlimits_{i = 1}^n |s_i| leq 10^6)。(s_i, t) 中仅包含小写字母。

---

如果我们直接上KMP，对于每个匹配串都求一个next，时间和空间都是爆炸的，这时候，我们就引入了AC自动机。

我们考虑KMP之所以不能在优秀的时间复杂度内求出，瓶颈在于多次求next，有什么办法优化呢？

我们考虑用匹配串建一棵trie树，通过维护一个指针来在这棵树上计算答案。

具体来说，我们维护一个fail指针，使我们在计算答案时可以通过跳指针来统计所有以当前节点字符结尾
的匹配串的答案，并在当前节点的子节点无法匹配时跳到可以匹配的节点继续匹配。

那么我们考虑怎么建这个fail指针。

直接说定义，fail指针指向与当前节点结尾的后缀匹配的树上最长前缀的结尾节点。

是不是和KMP的next很像？当然不会KMP也可以理解。

考虑为什么这样可以不重不漏统计所有答案。我们发现，如果当前节点所代表的匹配串与文本串匹配，那么根据fail指针定义，这个节点的fail指针指向的节点到根节点的链一定可以与文本串匹配，这是显然的，那么我们如果一直跳指针，在这个节点是结尾节点时累计答案即可。

对于fail指针的第二个作用，我们考虑如果当前节点的子节点没有能与文本串当前位置匹配的字符，我们通过跳fail指针，可以继续寻找与文本串下一个字符匹配，且前缀与文本串匹配的节点。

特别的，若当前节点fail无法指向任何节点，它的fail指针指向虚根 (0)。

显然，这一过程可以BFS实现，如果通过找到当前节点的父节点的fail指针指向的节点，我们将当前节点的fail指针指向这个节点的与当前节点字符相同的子节点即可，形式化的，即：

[fail[son[i]]=son[fail[i]] ]

匹配与建树过程是平凡的，与trie树流程大体相同，这里不做赘述。

代码 ：

#include<bits/stdc++.h> #define Robin 0 using namespace std; const int N=1e6+10; string s; string t; int n; struct Tree { 	int son[26]; 	int fail; 	int end; } Ac[N]; int cnt,ans;  inline void insertTree(string a) { 	int len=a.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		if(!Ac[now].son[a[i]-'a']) 			Ac[now].son[a[i]-'a']=++cnt;  		now=Ac[now].son[a[i]-'a']; 	} 	Ac[now].end++; }  inline void getfail() { 	queue<int> q; 	for(int i=0;i<26;i++) 	{ 		if(Ac[0].son[i]) 		{ 			Ac[Ac[0].son[i]].fail=0; 			q.push(Ac[0].son[i]); 		} 	}  	while(q.size()) 	{ 		int u=q.front(); 		q.pop(); 		for(int i=0;i<26;i++) 		{ 			if(Ac[u].son[i]) 			{ 				Ac[Ac[u].son[i]].fail=Ac[Ac[u].fail].son[i]; 				q.push(Ac[u].son[i]); 			} 			else Ac[u].son[i]=Ac[Ac[u].fail].son[i]; 		} 	} }  inline void query(string t) { 	int len=t.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		now=Ac[now].son[t[i]-'a']; 		for(int j=now;j && Ac[j].end!=-1;j=Ac[j].fail) 		{ 			ans+=Ac[j].end; 			Ac[j].end=-1; 		} 	} 	cout<<ans; 	exit(0); }  int main(){ 	// freopen("text.in","r",stdin); 	// freopen("text.out","w",stdout);     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 	cin>>n; 	for(int i=1;i<=n;i++) 	{ 		cin>>s; 		insertTree(s); 	} 	getfail(); 	cin>>t; 	query(t); 	return Robin; } 

优化：

注意：在阅读本部分之前请务必保证已经理解AC自动机基础实现

例题引入：

有 N 个由小写字母组成的模式串以及一个文本串 T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 T 中出现的次数最多。

本题多测。

---

思考刚才的统计答案过程，如果换成统计出现次数，那么每次统计时最差都会遍历整棵树，时间复杂度被卡到(O(n^2))级别，那我们就学了个滚木。

所以考虑优化

方法一：

观察上面fail指针更新答案过程，如果指向节点是匹配串结尾节点才会更新，暴力跳满显然很唐诗，所以我们考虑更新答案时只跳有贡献的节点。

具体而言，我们记录g指针，如果当前节点fail指针指向的节点是有贡献的，就把g指针指向它，否则直接指向当前节点fail指针指向节点的g指针指向的节点。有点绕，好好理解一下。

代码：

#include<bits/stdc++.h> #define Robin 0 using namespace std; const int N=1.5e5+10,M=155; struct Tree { 	int son[26]; 	int fail,g; 	vector<int> end; } Ac[N];  int ans[M]; string s[M]; string t; int n,cnt;  inline void insert_tree(string a,int id) { 	int len=a.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		if(!Ac[now].son[a[i]-'a']) Ac[now].son[a[i]-'a']=++cnt; 		now=Ac[now].son[a[i]-'a']; 	} 	Ac[now].end.push_back(id); }  inline void getfail() { 	queue<int> q; 	for(int i=0;i<26;i++) 	{ 		if(!Ac[0].son[i]) continue; 		Ac[Ac[0].son[i]].fail=0; 		q.push(Ac[0].son[i]); 	}  	while(q.size()) 	{ 		int u=q.front(); 		q.pop(); 		for(int i=0;i<26;i++) 		{ 			if(Ac[u].son[i]) 			{ 				int v=Ac[u].son[i]; 				Ac[v].fail=Ac[Ac[u].fail].son[i]; 				if(Ac[Ac[v].fail].end.size()) Ac[v].g=Ac[v].fail; 				else Ac[v].g=Ac[Ac[v].fail].g; 				q.push(v); 			} 			else Ac[u].son[i]=Ac[Ac[u].fail].son[i]; 		} 	} }  inline void query(string t) { 	int len=t.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		now=Ac[now].son[t[i]-'a']; 		 		for(int j=now;j;j=Ac[j].fail) 		{ 			for(auto it : Ac[j].end) 				ans[it]++; 		} 	} }  void cleartree() { 	queue<int> q; 	for(int i=0;i<26;i++) if(Ac[0].son[i]) q.push(Ac[0].son[i]); 	memset(Ac[0].son,0,sizeof(Ac[0].son)); 	while(q.size()) 	{ 		int u=q.front(); 		q.pop(); 		Ac[u].end.clear(); 		Ac[u].fail=Ac[u].g=0; 		for(int i=0;i<26;i++) if(Ac[u].son[i]) q.push(Ac[u].son[i]); 		memset(Ac[u].son,0,sizeof(Ac[u].son)); 	} 	cnt=0; }  int main(){ 	// freopen("text.in","r",stdin); 	// freopen("text.out","w",stdout); 	cin>>n; 	while(n) 	{ 		for(int i=1;i<=n;i++) 		{ 			cin>>s[i]; 			insert_tree(s[i],i); 		} 		getfail(); 		cin>>t; 		query(t); 		int res=0;  		for(int i=1;i<=n;i++) res=max(ans[i],res); 		cout<<res<<'n'; 		for(int i=1;i<=n;i++) 			if(ans[i]==res) cout<<s[i]<<'n';  		memset(ans,0,sizeof(ans)); 		cleartree(); 		cin>>n; 	} 	return Robin; } 

方法二：

注意到如果精心构造数据，那么上述优化还是会被卡，那么我们继续大力优化。

考虑拓扑图。

注意到，跳fail的过程还是会有重复跳的可能，所以考虑在这里优化。

我们把fail指针指向看成一条边，那么整个fail指针构成一棵fail树，当匹配到一个节点时，它的答案贡献于它到根的一条链，我们如果只在它身上记录贡献，匹配结束后跑拓扑排序将它祖先的答案更新就可以完美解决问题。

那么你搞定了这道题：AC自动机（二次加强版）

值得一提的是，对于第一种优化，除了最后一个hack以外，其他测试点跑的飞快，可见其优化效果还是不错的。

代码:

#include<bits/stdc++.h> #define Robin 0 using namespace std; const int N=2e5+10; int ans[N]; bool vis[N]; string s[N]; string t; struct Tree { 	int son[26]; 	int fail; 	int f; 	vector<int> end; 	// inline void init(){end.reserve();} } Ac[N]; int n,cnt; int in[N];  inline void insert_tree(string a,int id) { 	int len=a.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		if(!Ac[now].son[a[i]-'a']) Ac[now].son[a[i]-'a']=++cnt; 		now=Ac[now].son[a[i]-'a']; 	} 	Ac[now].end.push_back(id); }  inline void getfail() { 	queue<int> q; 	for(int i=0;i<26;i++) 	{ 		if(Ac[0].son[i]) 		{ 			Ac[Ac[0].son[i]].fail=0; 			q.push(Ac[0].son[i]); 		} 	}  	while(q.size()) 	{ 		int u=q.front(); 		q.pop(); 		for(int i=0;i<26;i++) 		{ 			if(Ac[u].son[i]) 			{ 				Ac[Ac[u].son[i]].fail=Ac[Ac[u].fail].son[i]; 				in[Ac[Ac[u].son[i]].fail]++; 				q.push(Ac[u].son[i]); 			} 			else Ac[u].son[i]=Ac[Ac[u].fail].son[i]; 		} 	} }  inline void query(string t) { 	int len=t.size(); 	int now=0; 	for(int i=0;i<len;i++) 	{ 		now=Ac[now].son[t[i]-'a']; 		if(now!=0) Ac[now].f++; 	}  	queue<int> q; 	for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i); 	while(q.size()) 	{ 		int u=q.front(); 		q.pop(); 		for(auto i : Ac[u].end) ans[i]+=Ac[u].f; 		int v=Ac[u].fail; 		Ac[v].f+=Ac[u].f; 		in[v]--; 		if(!in[v]) q.push(v); 	}  }  int main(){ 	// freopen("text.in","r",stdin); 	// freopen("text.out","w",stdout); 	cin>>n; 	for(int i=1;i<=n;i++) 	{ 		cin>>s[i]; 		insert_tree(s[i],i); 	}  	getfail(); 	cin>>t; 	query(t); 	for(int i=1;i<=n;i++) cout<<ans[i]<<'n'; } 

fail树：

在第二种优化中，我们提到，将fail指针看成边，建树，这实际上就是fail树。

在fail树上有很多性质，这使得我们可以利用这些性质解决一些问题。

通过将字符串问题转化为树上问题，就可以利用DP，数据结构，图论算法等解决问题。

例题：P2414 [NOI2011] 阿狸的打字机

通过将字符串匹配问题转化为子树和问题，用树状数组维护即可，具体解法可以参考题解，这里不做赘述。

结语 ：

AC自动机大体内容就这么多，众所周知，CCF不出串串（假的），所以AC自动机学不学都没用（笑）。

笑点解析：这篇是在CSP-S 2025之后发的AC自动机学习笔记，令人忍俊不禁。