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

KMP

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

作用大概是判断一个字符串 \(S \ ,len=n\) 是否是字符串 \(T \ ,len=m\) 的字串,并且找出 \(S\) 在 \(T\) 当中每一次出现的位置。

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

\(\text{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\)。

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


#include<bits/stdc++.h>
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.
		}
	}// calc f
}

AC自动机

咕咕咕

Reference

《算法竞赛进阶指南》

AC 自动机 - OI Wiki

上一篇:KMP模式匹配算法之 next[ ] 数组求值(天勤详解)


下一篇:KMP