【算法笔记】KMP和AC自动机

KMP

KMP是一种字符串匹配算法，也可以叫它模式匹配算法。

作用大概是判断一个模式串 $S \ ,len=n$ 是否是文本串 $T \ ,len=m$ 的子串，并且找出 $S$ 在 $T$ 当中每一次出现的位置。

要使用这个算法必须先知道一个十分重要的思想：$\text{next}$ 数组。

Next 指针

在跑KMP之前需要对于 $S$ 处理出这个东西（当然，这个东西会出现在很多字符串题里）。

它是一个类似于 AC 自动机的 $\text{fail}$ 指针的东西（都是在失配时用来转移）。

但是 $\text{next}_i$ 是求前缀 $S[1,i]$ 的最长的 Border （同时为原串前缀和后缀的一个子串）。

AC 自动机的 $\text{fail}$ 之后会说。

这个东西就是为了在失配的时候更快的进行下一步的匹配。

定义：$\text{next}_{i}=\max\{j\ |\ S[1,j]=S[i-j+1,i] \ , j\le i\}$

说白了，$\text{next}_i$ 就是对于 $S$ 的前缀 $S[1,i]$ ，能够把这个前缀分成两个完全相等的部分 $S[1\sim j]$ 和 $S[i-j+1 \sim i]$ 的最大位置 $j$。

如果不存在这样子的 $j$ ，那么 $\text{next}_i=0$。

为了方便叙述，定义这个满足条件 $S[1,j]=S[i-j+1,i]$ 的 $j$ 为 $\text{next}_i$ 的"候选项"。

你可以使用朴素的 $\text{O}(n^2)$算法来计算，但是这很明显不够啊，我们还不如不用它，直接暴力匹配 $S$ 和 $T$ 得了。

那么这个时候就有一个引理：

若 $j$ 是 $\text{next}_i$ 的一个候选项，那么满足 $j^\prime < j$ 的最大的 $\text{next}_i$ 的"候选项" $j^\prime$ 是 $\text{next}_j$ 。

证明使用反证法+画图即可。

也就是说 $(\text{next}_j,j)$ 这个开区间当中的数都不是 $\text{next}_i$ 的“候选项”。

用它可以对求 $\text{next}$ 的过程进行优化。

根据它可以发现，对于 $\text{next}_i$ ，他的所有候选项是 $\text{next}_i,\text{next}_{\text{next}_i},\text{next}_{\text{next}_{\text{next}_i}}...$

然后又有一个引理2：

如果 $j$ 是 $\text{next}_i$ 的一个“候选项”，那么 $j-1$ 一定是 $\text{next}_{i-1}$ 的”候选项“。

因为如果 $S[1,j]=S[i+j-1,i]$ ，那么肯定会有 $S[1,j-1]=S[i+(j-1)-1,i]$ 。

（画图即可证明）

那么我们在计算完 $\text{next}_{i-1}$ 之后，我们让 $\text{next}_i$ 的所有候选项变成 $\text{next}_{i-1}-1,\text{next}_{\text{next}_{i-1}}-1,\text{next}_{\text{next}_{\text{next}_{i-1}}}-1...$ 就可以了。

复杂度就变成了线性的。

实现

在有了 $\text{next}$ 之后，我们完成了对 $S$ 的自行匹配。

现在还需要做一个类似的过程，让 $S$ 和 $T$ 进行匹配。

我们定义 $f_i=\max\{j \ | \ T[i-j+1,i]=S[1,j] \ ,j \le i\}$。

如果 $f_i=n$ 那么就证明，$S$ 在 $T$ 中出现了一次，并且它出现在区间 $T[i-n+1,i]$。

我们类比上面 $\text{next}$ 的求法就能求出 $f$。

$\text{next}$ 的求法说通俗点就是：

假设 $\text{next}_{i-1}$ 已经求出来，那么尝试一直扩展这个 $j$ ，

如果说下一个位置 $j+1$ 无法满足 $S[j+1]=S[i]$ ，那么令 $j=\text{next}_j$ （失配），直到 $j=0$ 再停止。

如果说下一个位置是满足要求的，那么令 $j=j+1$。

也就是说，这个 $j$ 就是表示：模式串有多少位和文本串匹配上了。

那么 $j=n$ 的时候就代表匹配成功了。

复杂度是 $\text{O}(n+m)$。


#include
using namespace std;

const int si=1e6+10;
int n,m;
string s,t;
int Next[si],f[si];

int main(){
	Next[1]=0;
	cin>>s>>t;
	n=(int)s.size(),m=(int)t.size();
	s=' '+s,t=' '+t;
	for(register int i=2,j=0;i<=n;++i){
		while(j>0 && s[i]!=s[j+1]) j=Next[j];
		if(s[i]==s[j+1]) ++j;
		Next[i]=j;
	}// calc next
	for(register int i=1,j=0;i<=m;++i){
		while(j>0 && (j==n || t[i]!=s[j+1])) j=Next[j]; // 这里把 j==n 放到里面了，有些要你求 Border 的题要提出来写（比如lg3375）
		if(t[i]==s[j+1]) ++j;
		f[i]=j;
		if(f[i]==n){
			// S exist in T.
            //你也可以在某种情况下省去 f
		}
	}// calc f
}

AC自动机

这是一个多模式匹配算法，可以对于一个文本串同时匹配多个模式串。

先在讲之前澄清一个误区：

AC 自动机不就是在 Trie 上跑 KMP吗？

并不是的，你需要知道，AC 自动机是在 Trie 上建立的一个确定有限状态自动机（DFA）。

它只是利用到了一个和 KMP 的 $\text{next}$ 思想相似的 $\text{fail}$ 指针，并不是直接在 Trie 上面跑 KMP。

确定有限状态自动机（DFA）

英文名叫 Deterministic finite automaton

这是一个能够实现状态转移的自动机，在《离散数学》当中应该会涉及到。

它由以下的几个东西构成：

状态集合 $Q$
字符集 $\Sigma$
状态转移函数 $\delta : Q \times \Sigma \to Q$

也就是一个满足 $\delta(q,\sigma)=q^\prime, q\in Q,q^\prime \in Q,\sigma \in \Sigma$ 的函数。
开始状态 $\text{start}$
接收的状态集合 $F \subseteq Q$

它可以根据一个属于 $Q$ 的状态 $\text{state}$ 和一个属于 $\Sigma$ 的字符 $ch$ 转移到下一个状态（可以是先前的那个状态）

也就是通过 $\delta(\text{state},ch) $ 转移到下一个状态 $\text{state}^\prime$ 。

那么你只需要知道这些，其他的我们不会在 AC 自动机里面提到。

构建 Trie 树

在你进行匹配之前，我们首先要把初始的 Trie 树构建出来，并且搞清楚一些定义，方便之后的理解。

你知道 Trie 树是一个长成这样子的树：

它把字符储存在边上，节点则储存一个 $end$ 来标识一个单词的结尾。

在 AC 自动机当中，我们不仅让节点储存 $end$ 标记，还让 Trie 树的每一个节点代表某（几）个模式串的前缀，也称作一个”状态“ 。

这里实际上每一个节点就代表了 $\text{root}$ 到它的路径上的那个字符串。

而 Trie 树的字符指针（边）则是状态的转移（在下文会细说）。

我们在开始的时候把所有的模式串都丢到 Trie 树上，在之后把文本串放进去进行多模式匹配。

那么从 DFA 的角度来看，所有模式串所构建出的 Trie 树的所有状态所构成的集合就是 $Q$。

Trie 树的边就是状态转移函数 $\delta$ ，Trie 树的树根就是开始状态 $\text{start}$。

Fail 指针

也叫它失配指针，和 KMP 的 $\text{next}$ 指针类似，它也是在失配的时候进行转移的一个指针。

对于任意的一个状态 $u$ ，它的 $\text{fail}_u$ 会唯一地指向另外一个不等于 $u$ 的状态 $v$ 且满足 $v \in Q$ ，并且 $v$ 是 $u$ 的最长后缀。

注意 $\text{fail}$ 指针的指向是唯一的，它不会同时指向多个节点。

并且它绝对不会向 $u$ 的下层节点指（你总不可能说存在一个字符串使得它的后缀比它还长吧？）。

这里我用颜色标注出了所有”信息“。

你会发现，状态 $u=\{qaw\}$ 的 $\text{fail}$ 指针指向了状态 $v=\{aw\}$ 而不是状态 $k=\{w\}$。

是因为，虽然 $k$ 也是 $u$ 的后缀，但是有一个比他更长的后缀 $v$ 存在，所以 $\text{fail}_u$ 指向了 $v$。

那么如何求出 $\text{fail}$ 呢？我们一般使用 BFS 来构建它。

使用 BFS 的话，类似于 KMP 的 $\text{next}$ ，我们可以在求 $\text{fail}_u$ 之前求出所有比他深度小的节点的 $\text{fail}$ 用于计算。

（KMP 是不断跳 $\text{next}$ 的 $\text{next}$，而 AC 自动机则是不断跳 $\text{fail}$ 的 $\text{fail}$ ）

首先，我们先初始化，让所有的 $\text{fail}$ 都指向 $\text{root}$。

考虑当前节点是 $u$ ，它的父亲节点是 $p$ ，并且满足 $p$ 通过一个字符 $ch$ 走到 $u$ 即 $\text{trie}[p][ch]=u$。

并且我们假设深度小于 $u$ 的所有节点的 $\text{fail}$ 都已经通过 BFS 求出。

首先看第一种情况，如果 $\text{trie}[\text{fail}_p][ch]$ 存在，也就是存在一个从 $\text{fail}_p$ 指出的 $ch$ 字符的指针指向另外一个状态。

那么我们就直接让 $\text{fail}_u$ 指向 $\text{trie}[\text{fail}_p][ch]$ 。

因为 $p$ 这个状态一定是状态 $u$ 的一个前缀，而 $\text{fail}_p$ 是 $p$ 的后缀，那么如果 $\text{fail}_p$ 有一个字符指针为 $ch$ ，那么这个字符指针指向的状态一定是 $u$ 的后缀。

那如果 $\text{fail}_p$ 这个节点没有 $ch$ 这个字符指针呢？

那我们就用 KMP 的思想，我继续跳 $\text{fail}_{\text{fail}_p},\text{fail}_{\text{fail}_{\text{fail}_p}}...$ ！然后重复第一种情况的判断，直到有 $ch$ 为止！

如果真的找不到任何一个状态可以作为 $\text{fail}_u$ 的话，我们让 $\text{fail}_u$ 直接指向 $\text{root}$ 就行。

Trie 图优化

你发现，当你失配去跳 $\text{fail}$ 指针的时候，你可能会跳很多很多次才会跳到最终要寻找的节点。

那么在特殊构造的数据上可以让你跳得根本停不下来（

所以我们就在想，有没有可能能直接一步到位，直接找到要转移的状态是什么呢？

在上面说 Trie 树的构建的时候我们提到过， $\text{trie}[u][ch]$ 可以当作 DFA 的状态转移函数 $\delta (u,ch)$ 来对待。

那么我们现在就修改原本的 $\text{trie}$ 数组的定义。

它不再是简单的定义：字典树上的一个字符指针（边）。

而是说，状态 $u$ 加上字符 $ch$ 之后应该转移到的状态 $u^\prime$ 是哪里。

也就是 $\text{trie}[u][ch]=\delta(u,ch) \to u^\prime$ 。

之后，我们就将这个更改过定义的 $\text{trie}$ 数组称作 $\text{trans}$ 。（转移的意思）

具体怎么求呢？

还是在 BFS 的过程当中求。（我们仍然需要提前求出深度比当前节点小的所有节点的 $\text{fail}$）

设当前的节点是 $u$，你要去跳的字符是 $ch$，也就是现在要求 $\text{trans}[u][ch]$ 。

如果说 $\text{trans}[u][ch]$ 已经存在了（你可以理解为原来的字典树上已经有 $u$ 指向某个状态的 $ch$ 字符指针了）

那么令 $\text{fail}_{\text{trans[u][ch]}}=\text{trans}[\text{fail}_u][ch]$ ，并把 $\text{trans}[u][ch]$ 入队以便之后的扩展（不入队会出事）。

你发现按照之前的做法，我们需要不断的跳 $\text{fail}$ ，直到找到一个字符 $ch$ 的指针再赋值。

但是这里不要忘记了 $\text{trans}$ 的定义，它已经求出了 $\text{fail}_u$ 加上字符 $ch$ 应该去往的状态。

在实际实现的时候，我们就不需要再继续跳 $\text{fail}$ 指针了。

然后，如果 $\text{trans}[u][ch]$ 并不存在，我们让他指向 $\text{trans}[\text{fail}_u][ch]$ 就行了。

$\text{trans}$ 这个东西修改了字典树的结构，让它变成了一个字典图。

它相当于是把跳 $\text{fail}$ 的路径直接压缩，一步到位。

还有，我们说更改它的定义，并不是说你就不可以按照原来的 $\text{trie}$ 的定义去理解了（只是在更改 Trie 树的结构之后才需要换定义理解）。

你在看根节点（一般让根节点为 $0$）的 $\text{trans}$ 的时候就要用原来的定义理解（

比如说根节点有一个字符指针是 $ch$ ，那么 $\text{trans}[\text{root}][ch]$ 就等于原来的 $\text{trie}[\text{root}][ch]$。

现在来个例子理解一下（为了简单易懂去掉了一些信息）：

首先我们看状态 $u$ ，它的 $\text{trans}[u]['a']$ 已经存在了，也就是状态 $v$。

那么我们让 $\text{fail}_v$ 指向 $\text{trans}[\text{fail}_u]['a']$ 也就是 $\text{trans}[g]['a']=h$。

你会发现这个时候 $h$ 确实就是 $\text{fail}_v$ ，正确性是有保证的（至于原因的话用定义证明即可）。
然后看状态 $f$ ，它的 $\text{trans}[f]['c']$ 是不存在的，而 $\text{fail}_f=\text{root}$ ，所以我们让 $\text{trans}[f]['c']$ 指向 $\text{trans}[\text{root}]['c']$。

发现 $\text{root}$ 也没有这个 $\text{trans}$ ，所以我们让 $\text{trans}[\text{root}]['c']=\text{root}$。

那么最终就有 $\text{trans}[f]['c']=\text{root}$。
再看状态 $k$ ，它没有 $\text{trans}[k]['w']$，所以让它指向 $\text{trans}[\text{fail}_k]['w']$。

而 $\text{fail}_k=\text{root}$，发现已经有 $\text{trans}[\text{root}]['w']=g$。

所以让 $\text{trans}[k]['w']=g$ 即可。

当然，我上面说的 $\text{trans}$ 有些是要理解为原来的 $\text{trie}$ 数组的。

当在原来的 Trie 树上真实存在这条边的时候，$\text{trans}$ 就是原来的 $\text{trie}$ 的字符指针所指向的节点。

反过来，当原来不存在这条边（虚边）的时候，$\text{trans}$ 就会指向另外一个状态。

实现的话在下面（那里面的 build函数同时构建了 $\text{fail}$ 和 Trie 图）：

查询

查询有多少个不同的模式串在文本串里面出现过。

如果要问每一个的次数需要用到失配树。

其实这个玩意儿比较简单，和 Trie 树的查询是非常像的。

因为你是对于模式串建立的 AC 自动机，所以查询就需要把文本串丢进去查询。

当你每一次跑到一个有 $end$ 标记的点的时候，

统计一下答案，打上标记，然后按照类似 Trie 树的方式继续转移即可。

 // 完整版的 Luogu P3808
#include
using namespace std;

namespace Ac_Automaton{
	const int si=1e6+10;
	int root=0;
	int tr[si][27],tot=0;
	int End[si],fail[si];
	inline int cal(char ch){ return (int)(ch-'a')+1;}
	inline void init(){
		memset(End,0,sizeof End);
		memset(fail,0,sizeof fail);
		memset(tr,0,sizeof tr);
		tot=0;
	}
	inline void insert(char *s){
		int u=0;
		for(register int i=1;s[i];++i){
			if(!tr[u][cal(s[i])]) tr[u][cal(s[i])]=++tot;
			u=tr[u][cal(s[i])];
		}++End[u];
	}
	queueq;
	inline void build(){
		for(register int i=1;i<=26;++i){
			if(tr[root][i]) q.push(tr[root][i]);
		}// 注意这里是把root的所有儿子节点入队，不然跳Fail会死循环
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(register int i=1;i<=26;++i){
				if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
	inline int query(char *t){
		int u=0,res=0;
		for(register int i=1;t[i];++i){
			u=tr[u][cal(t[i])];
			for(register int j=u;j && End[j]!=-1;j=fail[j]){
				res+=End[j],End[j]=-1;
			}
		}return res;
	}
}using namespace Ac_Automaton;

int n;
char s[si],t[si];
int main(){
    init();
	scanf("%d",&n);
	for(register int i=1;i<=n;++i){
		scanf("%s",s+1);insert(s);
	}
	scanf("%s",t+1);
	build();
	printf("%d\n",query(t));
	return 0;
}

Fail 树

这个东西可以解决“每一个模式串分别在文本串里出现多少次”的问题。

你知道的， $\text{fail}$ 指针只会唯一指向一个节点，也就是说每一个点的出度是 $1$。

那么我们把所有指针反向，每一个点的入度就是 $1$ 。

我们再令反向后指针的出发点为 $father$，指针指向的节点为 $son$ 。

我们就可以得到一颗以 $\text{root}$ 为根的树，称之为失配树（$\text{fail}$ 树）。

当我们把 $\text{fail}$ 树建出来之后，会有很多很多利于我们查询的性质。

我们知道，你在 query 里面跳节点 $u$ 的 $\text{fail}$ 的时候，你相当于就是在查找构成状态 $u$ 的后缀里面有没有其他的模式串。

又因为 $\text{fail}_u$ 的定义是 $u$ 在自动机上的最长真后缀，所以我们把 $\text{fail}$ 倒过来之后，

$\text{fail}$ 指向的状态就是 $\text{fail}$ 指出的状态的、在AC自动机上的最长真后缀。

那么我们就观察 $\text{fail}$ 树上每一个节点和它的子树的关系：

你会发现两个比较显然的性质：

$u$ 的子树当中的所有节点都有 $u$ 这个真后缀（注意不一定是最长，只是普通的真后缀）。
$u$ 的子树之外的节点都没有 $u$ 这个真后缀。

这些性质可以拿来干啥呢？

我们假设 $u$ 就刚好是一个模式串，那么你会发现，$u$ 就是 $\{x,y,z,g,f,e,w\}$ 这几个前缀的后缀。

也就是说如果我们把文本串丢上来匹配的时候，如果跳到了这些节点，就证明 $u$ 这个状态所代表的模式串在文本串里面出现了一次。

而我们把第一个结论推广一下，我们可以发现：

$u$ 的所有真后缀，就是 $u$ 的所有祖先节点所代表的前缀。

那对于匹配时每一次跳到的节点，我们都进行统计，不就可以统计每一个模式串在文本串里面出现的次数了吗？

也就是只需要 $\texttt{dfs}$ 一次 $\text{fail}$ 树就行了。

具体来说，记录自动机上的每个状态被匹配了几次，最后求出每个模式串在 Trie 树上的终止节点在 $\text{fail}$ 树上的子树的总匹配次数就可以了。

因为 $u$ 的子树都有 $u$ 这个真后缀，然后当它在 $\text{fail}$ 树上的子树的节点被匹配到一次之后，那 $u$ 不就在文本串里面出现了一次吗？

当然，你也可以使用链表一类的 DS 辅助你解决问题。

具体就看代码理解吧。

 // Luogu P5357
#include
using namespace std;

int n;
namespace Ac_Automaton{
	const int si=2e6+10;
	int root=0,tot=0,cnt_f=0;
	int tr[si][27];
	int End[si],fail[si],cnt[si];
	inline int cal(char ch){ return (int)(ch-'a')+1;}
	inline void init(){
		memset(End,0,sizeof End);
		memset(fail,0,sizeof fail);
		memset(tr,0,sizeof tr);
		memset(cnt,0,sizeof cnt);
		tot=0;
	}
	inline void insert(char *s,int nu){
		int u=0;
		for(register int i=1;s[i];++i){
			if(!tr[u][cal(s[i])]) tr[u][cal(s[i])]=++tot;
			u=tr[u][cal(s[i])];
		}End[nu]=u; // 这里改为记录第 nu 个模式串的结尾的位置。
	}
	struct Fail_Tree{
		int ver,Next,head;
	}ft[si<<1];
	inline void add(int u,int v){
		ft[++cnt_f].ver=v,ft[cnt_f].Next=ft[u].head;
		ft[u].head=cnt_f;
	}
	queueq;
	inline void build(){
		for(register int i=1;i<=26;++i){
			if(tr[root][i]) q.push(tr[root][i]);
		}
		while(!q.empty()){
			int u=q.front();
			add(fail[u],u),q.pop(); // 构建 Fail 树
			for(register int i=1;i<=26;++i){
				if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
	inline void dfs(int u,int fa){
		for(register int i=ft[u].head;i;i=ft[i].Next){
			int v=ft[i].ver;
			if(v==fa) continue;
			dfs(v,u),cnt[u]+=cnt[v];
		} // 统计 
	}
	inline void query(char *t){
		int u=0;
		for(register int i=1;t[i];++i){
			u=tr[u][cal(t[i])],++cnt[u];
		} // 记录每个状态被匹配多少次
		dfs(root,-1);
		for(register int i=1;i<=n;++i){
			printf("%d\n",cnt[End[i]]);
		}
	}
}using namespace Ac_Automaton;

char s[si],t[si];

int main(){
    init();
	scanf("%d",&n);
	for(register int i=1;i<=n;++i){
		scanf("%s",s+1);insert(s,i);
	}
	scanf("%s",t+1);
	build(),query(t);
	return 0;
}

例题及其讲解

P5231 [JSOI2012]玄武密码
P3966 [TJOI2013]单词
P2414 [NOI2011] 阿狸的打字机
P2292 [HNOI2004]L语言
P2536 [AHOI2005]病毒检测

Reference

《算法竞赛进阶指南》

AC 自动机 - OI Wiki

AC自动机相关&Fail树（转载自55242.cf）

(https://www.luogu.com.cn/blog/ouuan/solution-p5357)

Mao_Zx && Guo_Jh 神仙的字符串友情讲解

Type-算法笔记 Cate-字符串 Algor-KMP Algor-AC自动机