本文共 6608 字，大约阅读时间需要 22 分钟。

$引入$

“ SY 和 WYX 在看毛片。（几 毛 钱买到的动作 片，毛 片）

WYX 突然想回味一个片段，但是只记得台词里面有一句挺长的 “ $\ast \ast \ast \ast$ ”，于是，他们找到剧本，想看 “ $\ast \ast \ast \ast$ ”在剧本中出现了几次，分别是在什么地方。

他们遇到了麻烦，这样的剧本随便就是数百万单词，数千万字母，而且 “ $\ast \ast \ast \ast$ ”长度也有上千万。

为了解决这个问题，SY 发明了一个 O(N) 的字符串匹配算法，以这次的目的命名，就叫 KMP(看毛片) 算法。 ”

但是他们不知道，前人已经发明此算法：

KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作，简称 KMP 算法。

——摘自

“ 气愤的 SY 只好继续看毛片，并顺便拿了 NOIP2020提高组 CQ前十 ”

$KMP算法讲解$

引入里面讲的很形象了，$KMP$ 算法是用来解决字符串匹配问题的，

暴力怎么做的不用我说了吧，咱们直接进入正题。

$KMP$ 算法由两个子任务组成，求 $S2$ 每个前缀的最长 $border$ 和 在 $S1$ 中匹配 $S2$ 。

Subtask 1 求 border（求 next ）

$border$ 是 “边界” 的意思，字符串内既是前缀又是后缀（而不等于原串）的一个子串，形象地叫它为该字符串的 $border$.

例：

1. abcab d abcab
2. SY is such a SY

上面两个字符串中加粗的地方就是该字符串的最长 $border$，字符串的 $border$ 并不唯一，比如第一个字符串就还有另一个 $border$ ：“ ab ”，但是不是最长的。

根据这个定义，我们可以想想怎么线性地求 $S2$ 每一个前缀的最长 $border$ 的长度。

在 $KMP$ 算法中，我们定义 $S$ 第 $i$ 个前缀的最长 $border$ 的长度为 $nex{t}_S[i]$ （为什么叫 “next”，笔者也很好奇 🙃）

从字符串前端算起，很明显，由于 $next[i]<i$，所以 $next[0]=next[1]=0$.

然后往后算，设当前算到的位置为 $i$ ，

首先，如果 $S[i]==S[next[i-1]+1]$ ，那么 $next[i]=next[i-1]+1$ ，而且这是 $next[i]$ 最好的情况，可以直接完事，去求 $i+1$ 了，因为如果 $next[i]>next[i-1]+1$ 的话，$next[i-1]$ 肯定可以等于 $next[i]-1$.

（next[i] : #### # #### $\to$ next[i-1] : #### # ###(#)）

那么否则就得找 $i-1$ 的次大的 $border$ ，以此类推。由于次大的 $border$ 肯定满足是最大的 border 的前缀且后缀，因为：

1. 该 $border$ 对应最大 $border$ 前缀部分的前缀：AAAA B AAAA
2. 该 $border$ 对应最大 $border$ 后缀部分的后缀：AAAA B AAAA
3. 最大 $border$ 前缀部分和后缀部分显然相同：AAAA B AAAA

于是，可以充分证明，若当前的 $border$ 大小为 $x$ ，则次大的 $border$ 为 $next[x]$ （前缀部分的 $next$）。

好，我们就可以处理出 $S$ 每一个位置的 $next$ 了。

那为什么它是线性的呢？我们可以隐约地意识到，每个位置的 $next$ 没有向左扩展的过程，只有向右扩展，

由于 $next[i]\le next[i-1]+1$ ，所以整个计算过程中，$“i-next[i]”$ 这个量就从来没下降过，而且除了一开始判断 $“S[i]==S[next[i-1]+1]”$ 可能使该量不变以外，找次大 $border$ 的操作每次一定会使 $“i-next[i]”$变大，因此它是线性的。

模板

void INIT(char *ss,int *nxt,int n) {
   	nxt[0] = nxt[1] = 0;	for(int i = 2;i <= n;i ++) {
   		int nm = nxt[i-1]; nxt[i] = 0;		while(nm && ss[nm+1] != ss[i]) nm = nxt[nm];		if(ss[nm+1] == ss[i]) nxt[i] = nm+1;	}	return ;}

Subtask 2 字符串匹配

$KMP$ 算法实际上是通过求出 $S1$ 每一个位置 $i$ 向前延伸出最长的一段，满足是 $S2$ 的前缀，如果该段长度 $=lengt{h}_{S2}$ ，那么 $[i-lengt{h}_{S2}+1,i]$ 就是 $S2$ 的一个出现位置，也就是说 $KMP$ 是间接地解决了这个问题，这表明着该算法的功能可以更强大。

怎么做呢

仿照着求 $next$ 的推导，我们来求这个……不妨定义它为 $F$ 吧，设 $F[i]$ 为位置 $i$ 向前延伸出最长的一段，满足是 $S2$ 的前缀的长度。

从左到右依次计算吧，首先 $F[0]=0$.

接下来对于过程中的 $i$ ，如果 $S1[i]==S2[F[i-1]+1]$ 那么 $F[i]$ 直接等于 $F[i-1]+1$ 完事，否则找 $next[F[i-1]]$，然后是 $next[next[F[i-1]]]$ ……直到后面那一位符号匹配。

这时候就会发现 $next[]$ 有多么大的用处，因为其又是后缀又是前缀的性质，使得 $i$ 可以正常地从 $F[i-1]$ 的一个 $border$ 出转移过来。

它的复杂度和正确性都和 $next$ 的证明类似，而且大多数人其实是第一部分看不懂而已，那就留给读者们一个思考空间吧🐵（笔者要写扩展KMP了……）

模板

//这里的代码特别灵活，每个题都不一样，笔者就不贴了

$exKMP算法讲解$

“加了 ‘ex’前缀的算法总会变得高端一些呢 ”

前面说了，$KMP$ 算法是求 “ $S1$ 每一个位置 $i$ 向前延伸出最长的一段，满足是 $S2$ 的前缀的长度 ” ，而扩展 $KMP$ 则是求 “ $S1$ 每一个位置 $i$ 向后延伸出最长的一段，满足是 $S2$ 的前缀的长度 ” ，即，$S1$ 每个后缀与 $S2$ 的最长公共前缀。

该算法也有两个子任务，求 $S2$ 每个后缀和 $S2$ 本身的最长公共前缀长度 和 在 $S1$ 每个后缀中匹配 $S2$（如上）.

Subtask 1 ···

不妨设 $ex[i]$ 为 $S2i$ 开头的后缀和 $S2$ 本身的最长公共前缀长度，然后我们开始想怎么线性求它。

首先，$ex[1]=lengt{h}_{S2}$，$ex[2]$ 可以暴力求出来。

接下来往后算，到了当前位置 $i$ ，若 $ex[i-1]-1>ex[2]$ ，则 $ex[i]=ex[2]$。

但是这并不能很好地衔接 $i+1$ ，因为这样一来直接进入 $i+1$ 的话就要回退了，所以我们继续再判断是否 $ex[i-1]-1>ex[3]$（决定 $ex[i+1]$ ） …… 最后起码会止步于 $ex[i-1]-1>ex[i-1]$ 的判断（因为这肯定不成立），因此不存在访问了未计算部分的情况。

要是对于决定 $ex[i+x-2]$ 的判断， $ex[i-1]-1\le ex[x]$ 呢？那就暴力从 $i+ex[i-1]-2$ 再向右扩展就是了。这样一来就不会向左回退，只会向右扩展，保证了复杂度线性。

模板

void INITex(char *ss,int *ex,int n) {
   	ex[0] = 0;ex[1] = n;ex[2] = 0;	int l = 0,r = 0;	for(int i = 2;i <= n;i ++) {
    ex[i] = 0;		if(i <= r) ex[i] = min(ex[i-l+1],r-i+1);		while(i + ex[i] <= n && ss[i+ex[i]] == ss[ex[i]+1]) ex[i] ++;		if(i + ex[i] - 1 > r) l = i,r = i + ex[i] - 1;	}	return ;}

Subtask 2 ···

也可以仿照 $ex[]$ 的计算。

不妨设 $G[i]$ 为 $S1$ 的第 $i$ 位的后缀与 $S2$ 的最长公共前缀。

类似地，首先，$G[1]$ 可以暴力跑出来。

然后，遍历到每一个 $i$ ，若 $G[i-1]-1>ex[2]$ （注意这里是 $ex[2]$），则 $G[i]=ex[2]$，然后继续判是否 $G[i-1]-1>ex[3]$ 来决定 G[i+1] …… 这里就不用担心未计算的问题，因为 $ex[]$ 肯定都处理完了。

直到找到一个不成立的，就从 $i+G[i-1]-2$ 再向右找，和 $Subtask1$ 类似。

模板

for(int i = 1;i <= n;i ++) {
   if(s2[i] == s1[i]) G[1] = i;else break;}int l = 1,r = G[1];for(int i = 2;i <= n;i ++) {
    G[i] = 0;	if(i <= r) G[i] = min(ex[i - l + 1],r - i + 1);	while(i + G[i] <= n && s1[i + G[i]] == s2[G[i] + 1]) G[i] ++;	if(i + G[i] - 1 > r) l = i,r = i + G[i] - 1;}

转载地址：https://blog.csdn.net/weixin_43960414/article/details/110744238 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！