KMP 算法

KMP 算法不是看毛片算法，而是一种字符串匹配算法. KMP 是此算法的发明者 Kruth，Morris 和 Pratt 的名字缩写.

给定字符串 $A$（长度为 $m$）和 $B$（长度为 $n$），问 $A$ 中是否包含 $B$ ？

$$\begin{aligned} A&=a \ b \ a \ b \ a \ b \ a \ b \ c\\ B&=a \ b \ a \ b \ c \end{aligned}$$

考虑暴力算法：

• 先将 $A$ 和 $B$ 左端对齐.
• 如果匹配失败，就将 $B$ 右移一位，直到匹配成功.

$$\begin{aligned} A&=\textcolor{red}{a \ b \ a \ b \ a} \ b \ a \ b \ c\\ B&=\textcolor{red}{a \ b \ a \ b \ c} \end{aligned}$$

$$\begin{aligned} A=a \ &\textcolor{red}{b \ a \ b \ a \ b} \ a \ b \ c\\ B=\;&\textcolor{red}{a \ b \ a \ b \ c} \end{aligned}$$

$$\begin{aligned} A=a \ b \ &\textcolor{red}{a \ b \ a \ b \ a} \ b \ c\\ B=\;&\textcolor{red}{a \ b \ a \ b \ c} \end{aligned}$$

$$\begin{aligned} A=a \ b \ a \ &\textcolor{red}{b \ a \ b \ a \ b} \ c\\ B=\;&\textcolor{red}{a \ b \ a \ b \ c} \end{aligned}$$

$$\begin{aligned} A=a \ b \ a \ b \ &\textcolor{green}{a \ b \ a \ b \ c}\\ B=\;&\textcolor{green}{a \ b \ a \ b \ c} \end{aligned}$$

时间复杂度：$O(mn)$.

本章统一使用红色表示不匹配，绿色表示匹配.

bool match(string a, string b) {
    int m = a.size(), n = b.size();
    int i = 0, j = 0;
    while(i < m) {
        while(j < n && a[i] == b[j]) j ++;
        if(j == n) return true;
        i ++, j = 0;
    }
    return false;
}

当匹配失败时，我们忽视了一些重要的信息.当第一次匹配失败时，两个绿串相等.

$$\begin{aligned} A&=\textcolor{green}{a \ b \ a \ b} \ \textcolor{red}{a} \ b \ a \ b \ c\\ B&=\textcolor{green}{a \ b \ a \ b} \ \textcolor{red}{c} \end{aligned}$$

该绿串还有着相同的前缀¹和后缀.我们管它叫做「公共前后缀」. $abab$ 的公共前后缀为 $ab$.

$$\underset{\large前缀}{\underline{\textcolor{green}{a \ b}}} \ \underset{\large后缀}{\underline{\textcolor{green}{a \ b}}}$$

从下面这个角度看，$A$ 和 $B$ 划线的两段，都是公共前后缀，它们相等.

$$\begin{aligned} A&=a \ b \ \underline{\textcolor{green}{a \ b}} \ a \ b \ a \ b \ c\\ B&=\underline{\textcolor{green}{a \ b}} \ a \ b \ c \end{aligned}$$

若 $B$ 右移后能与 $A$ 匹配，那么 $B$ 至少要右移 $2$ 位，也就是使相等的两段对齐.这样就避免了一位一位地移，从而提高效率.

$$\begin{aligned} A=a \ b \ &\underline{\textcolor{green}{a \ b}} \ a \ b \ a \ b \ c\\ B=\;&\underline{\textcolor{green}{a \ b}} \ a \ b \ c \end{aligned}$$

到此为止，KMP 的思路已经很明朗了.

现在还有一个问题：在程序中，如何实现字符串的右移？—— 使用指针.

指针 $i,j$ 分别指向 $A$ 串和 $B$ 串，表示 $A[i]$ 和 $B[j]$ 前的两个绿串匹配.如果将 $B$ 串右移 $x$ 位，那么在程序中，只需要将 $j$ 指针左移 $x$ 位.

$$\begin{aligned} A&=\textcolor{green}{σσσσσ}\overset{\overset{i}{↓}}{\textcolor{red}{σ}}σσσσσσ\\ B&=\textcolor{green}{σσσσσ}\underset{\underset{j}{↑}}{\textcolor{red}{σ}}σ \end{aligned}$$

$$\begin{aligned} A=σσσ\textcolor{green}{σσ}\overset{\overset{i}{↓}}{σ}&σσσσσσ\\ B=\textcolor{green}{σσ}\underset{\underset{j}{↑}}{σ}&σσσσ \end{aligned}$$

$pre[i]$ 表示 $B[0\cdots i]$ 的公共前后缀长度，$pre[ \ ]$ 具体怎么预处理后续会说.现在假设 $pre[ \ ]$ 数组已经处理好了.依照刚才的思路，KMP 的主程序可以分解为以下步骤（结合下面的样例理解）：

1. 令 $i,j$ 分别指向 $A$ 和 $B$ 的开头，即 $i=0,j=0$.

2. 如果 $A[i]=B[j]$，$i$ 和 $j$ 同时右移一位.

3. 如果 $A[i]\not=B[j]$，又分两种情况讨论：

• $j\not=0$ 时，绿串的公共前后缀长度为 $pre[j-1]$.那么就令 $j=pre[j-1]$.

• $j=0$ 时，$j$ 不能再往左移.此时只能将 $i$ 右移一位.

4. 重复 2、3 两个步骤，直到匹配完成.

int pre[];

bool kmp(string A, string B) {
	int i = 0, j = 0;
	while(i < A.size()) {
		if(A[i] == B[j]) i ++, j ++;
		else if(j) j = pre[j - 1];
		else i ++;
		if(j == B.size()) //匹配成功
            return true;
	}
    return false;
}

$pre[ \ ]$ 数组的求法和 KMP 的主程序很相似.

指针 $i,j$ 都指向 $B$ 串，表示当前求的是 $B[0\cdots i]$ 的公共前后缀长度 $pre[i]$.并且 $B[0\cdots i]$ 的公共前后缀为 $B[0\cdots j]$，即 $pre[i]=j+1$.

因为 $pre[0]=0$ 不用求，所以直接从 $pre[1]$ 开始求就好，初始时 $i=1,j=0$.

$$\begin{aligned} B&=\overset{\overset{ i}{↓}}{aba}bc\\ B&=\underset{\underset{ j}{↑}}{a}babc \end{aligned}$$

然后，我们直接采用 KMP 主程序 的策略：

1. 如果 $B[i]=B[j]$，那么 $pre[i]=j+1$，并将 $i$ 和 $j$ 同时右移一位.

2. 如果 $B[i]\not=B[j]$，又分两种情况讨论：

   • $j\not=0$ 时，绿串的公共前后缀长度为 $pre[j-1]$.那么就令 $j=pre[j-1]$.

   • $j=0$ 时，绿串长度为 $0$，$j$ 不能再往左移了.此时只能将 $i$ 右移一位.

3. 重复前两步，直到 $pre[ \ ]$ 全部求完.

为什么可以这么做呢？因为仅当 $B[i]$ 和 $B[j]$ 前的若干个字符相匹配时，$B[0\cdots j]$ 才可能是公共前后缀.而 KMP 的主程序能够维护这一特征.

$$\begin{aligned} B&=ab\underline{\textcolor{green}{ab}}\overset{\overset{ i}{↓}}{c}\\ B&=\underline{\textcolor{green}{ab}}\underset{\underset{ j}{↑}}{a}bc \end{aligned}$$

也就是说，预处理 $pre[ \ ]$ 数组，和 KMP 的主程序，其实是在干同一件事情.

int pre[];

void getPre(string B) {
	int i = 1, j = 0; // 注意 i = 1
	while(i < B.size()) {
		if(B[i] == B[j]) pre[i] = j + 1, i ++, j ++;
		else if(j) j = pre[j - 1];
		else i ++;
	}
}