KMP

概念

介绍

作用：处理字符串匹配问题，即B是否是A的子串

暴力做法最坏时间复杂度O(nm)。

KMP最坏时间复杂度O(n)。

流程

用一个例子来说明。

$A=$ abababaababacb $B=$ ababacb

用两个指针 $i,j$ 分别表示 $A[i-j+1...i]$ 和 $B[1...j]$ 完全相等。

接下来检验 $A[i+1]$ 和 $B[j+1]$ 的关系，若两者相等，则都加 $1$；此时如果 $j=m$，则 $B$ 是 $A$ 的子串，并且得到匹配位置。否则，KMP的策略是调整j的位置（减小j值），使得 $A[i-j+1...i]$ 和 $B[1...j]$ 保持匹配并且尝试匹配新的 $A[i+1]$ 和 $B[j+1]$。

例如，$i=j=5$，情况如下：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = a b a b a c b

j = 1 2 3 4 5 6 7

此时 $A[6]!=B[6]$。这表明 $j$ 不能是 $5$ 了，我们要把 $j$ 减小成 $j'$，那么 $j'$ 可以是多少呢？

显然，$j'$ 必须要使得 $B[1..j]$ 中的头 $j'$ 个字母和末 $j'$ 个字母完全相符（保持 $i$ 和 $j$ 的性质），且 $j'$ 尽可能大（匹配得尽可能长）。

由于 $B[1...5]=$ ababa，头 $3$ 个字母和末 $3$ 个字母都是aba。而当新的 $j$ 为 $3$ 时，$A[6]=B[4]$，于是可以将 $i$ 变 $6$，而 $j$ 变成 $4$ ：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = $\ \ \ \ \ \$ a b a b a c b

j = $\ \ \ \ \ \ \$ 1 2 3 4 5 6 7

事实上，$j$ 取多少和 $i$ 无关，只和 $B$ 串本身有关。因此，可以预处理一个数组 $P[j]$ 表示匹配到第 $j$ 个字母而第 $j+1$ 个字母不匹配时，可以回退到的最大的 $j$。

$P[j]$ 应该是所有满足 $B[1...k]=B[j-k+1...j]$ 的 $k(k<j)$ 的最大值。

继续考虑刚刚的例子，由于 $A[7]=B[5]$， $i$ 和 $j$ 各增加 $1$，然后出现 $A[i+1] \ne B[j+1]$ 的情况：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = $\ \ \ \ \$ a b a b a c b

j = $\ \ \ \ \$ 1 2 3 4 5 6 7

由于 $P[5]=3$，所以 $j$ 回退到 $3$：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = $\ \ \ \ \ \ \ \ \ \ \$ a b a b a c b

j = $\ \ \ \ \ \ \ \ \ \ \ \$ 1 2 3 4 5 6 7

此时 $A[i+1] \ne B[j+1]$，而 $P[3]=1$，回退到 $j=1$：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ a b a b a c b

j = $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 1 2 3 4 5 6 7

此时 $A[i+1] \ne B[j+1]$，而 $P[1]=0$，回退到 $j=0$：

i = 1 2 3 4 5 6 7 8 9 ...

A = a b a b a b a a b a b ...

B = $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ a b a b a c b

j = $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 0 1 2 3 4 5 6 7

此时终于有 $A[8]=B[1]$，$i$ 和 $j$ 各自加 $1$。

事实上，存在 $j=0$ 但 $A[i+1] \ne B[1]$ 的情况，此时我们只增加 $i$，而不改变 $j$。

代码如下：

j=0;
for(int i=0;i<n;++i){
	//无法匹配且j>0，减小j 
	while(j>0&&B[j+1]!=A[i+1]) j=P[j];
	//能继续匹配，增加j 
	if(B[j+1]==A[i+1]) ++j;
	if(j==m){
		ans[++cnt]=i+1-m+1; //子串串首在母串的位置 
		j=P[j]; //继续匹配 
	}
}

时间复杂度

那么，为什么这个匹配过程是线性时间复杂度的呢？

由于for循环中，每一次循环j最多加1，所以整个过程最多加了n次1。

因此，j最多被减去n次，即程序第3行的while循环最多执行n次。

由于外层循环是O(n)的，while循环的最多执行次数也是n次，因此整个算法的时间复杂度是O(n)的。

预处理数组P

还有一个问题，如何预处理数组P？

可以通过前面的P值来求后面的P值。实际上，这个预处理过程和主程序几乎完全一致，KMP的预处理过程实际上就是B串“自我匹配”的过程。

代码如下：

P[1]=j=0;
for(int i=0;i<n;++i){
	//无法匹配且j>0，减小j 
	while(j>0&&B[j+1]!=B[i+1]) j=P[j];
	//能继续匹配，增加j 
	if(B[j+1]==B[i+1]) ++j;
	P[i+1]=j;
}

适用范围

KMP特点：只预处理B串。

适用：给定一个B串和一些不同的A串，问B串是哪些A串的子串。

例题

A. 剪花布条

字串匹配，显然是KMP题。

注意本题需要匹配不重叠子串，所以每次匹配到之后要将j变为0。

B. Power String

是个字符串自身匹配的问题，考虑使用KMP算法中的预处理部分。

设模式串的第i位和文本串的第j位不匹配，则需要回到第p[i]位重新和文本串第j位匹配，那么模式串第1到p[i]位和模式串(i-p[i])到i位是匹配的。所以说，模式串的1~p[n]位和模式串的(n-p[n])位到n位是匹配的。即，如果(n-p[n])%p[n]==0，那么存在重复连续子串，长度为n-p[n]，循环次数为n/(n-p[n])。

例：长为20的字符串abcdabcdabcdabcdabcd，可以分为5部分ABCDE，每部分都是abcd。由于p[n]=16，即ABCD段=BCDE段，可得A=B=C=D=E，所以存在重复连续子串且长度为4。

C. Radio Transmission

和例2类似的思路，相当于例2的弱化版。

最小循环节直接就是n-p[n]，注意一下下界即可。

D. OKR-Periods of Words

首先明确题目意思，题目意思是找到A的一个前缀Q，将这个前缀重复一遍之后，A变成了这个重复之后字符串的前缀。

匹配子串满足KMP算法中“前缀等于后缀”的性质，我们要使子串最长，那么这个匹配长度应该尽可能小。

但是KMP只能求出每个前缀串的最长匹配长度，如果要求出最短匹配长度，我们可以一直递推p[i],p[p[i]]...，直到为0。那么，前一个不是0的p就是答案。

记得开long long。

E. 似乎在梦中见过的样子

本题数据范围比较小，可以直接暴力。

暴力枚举合法字符串的左端点，然后从左端点开始的子串跑一遍KMP即可。

但是本题中，对于任意公共前后缀，我们在这题中并不希望它最长，而希望它在满足长度 ≥k 的情况下越短越好。

假设我们枚举左端点l,s长度为r，则形成的新子串为s[l...r]。

由题意我们可以知道，如果s[l...i]=s[j-i+l...j]且(i-l+1)>=k且l-1+(i-l+1)×2+1<=j，那么s[l...j]就是一个满足条件的子串。

如果直接暴力用p[i]找满足条件的前缀，时间复杂度会变成O(n^3)。

所以这个地方得继续用kmp的思想：当发现现在的i不满足条件时，可以用p[i]向前寻找满足条件的i。这样一来，总时间复杂度变成了O(n^2)。

F. Censoring

字符串匹配，直接想到KMP。

这题在匹配之后，需要删除掉匹配到的串，重新进行匹配。但是要是从头开始，显然很慢。

所以可以开一个辅助数组pos，pos[i]表示S的第i位匹配到的T的长度。

举个例子：whatthemomooofun中第9位pos[9]=2，匹配了mo。

这样我们每次在成功匹配退栈后可以让j跳向栈顶的pos，表示从栈顶继续匹配，保证匹配比较有效率。

本题有个较难的版本，但是需要AC自动机。

作业