简介

KMP 是一种快速的字符串匹配算法，是其发明者 Kruth，Morris 和 Pratt 的名字缩写。

问题

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

$$\begin{array}{rl}A& =ababababc\\ B& =ababc\end{array}$$

考虑暴力算法：

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

$$\begin{array}{rl}A& =ababababc\\ B& =ababc\end{array}$$$$\begin{array}{rl}A=a& babababc\\ B=& ababc\end{array}$$$$\begin{array}{rl}A=ab& abababc\\ B=& ababc\end{array}$$$$\begin{array}{rl}A=aba& bababc\\ B=& ababc\end{array}$$$$\begin{array}{rl}A=abab& ababc\\ B=& ababc\end{array}$$

时间复杂度：$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;
}

KMP 算法可以将此复杂度优化到 $O(n)$。

原理

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

$$\begin{array}{rl}A& =ababababc\\ B& =ababc\end{array}$$

该绿串还具有相同的前缀^[1]和后缀，称作「公共前后缀」。$abab$ 的公共前后缀为 $ab$。

$$\begin{array}{rl}A& =ab\underset{―}{ab}ababc\\ B& =\underset{―}{ab}abc\end{array}$$

若 $B$ 右移后能与 $A$ 匹配，那么 $B$ 至少要右移 $2$ 位，也就是使公共前后缀对齐。这样就避免了一位一位地移，从而提高效率。

$$\begin{array}{rl}A=ab& \underset{―}{ab}ababc\\ B=& \underset{―}{ab}abc\end{array}$$

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

将 $A$ 串和 $B$ 串左端对齐（$\sigma$ 表示不定字符）。

$$\begin{array}{rl}A& =\sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \\ B& =\sigma \sigma \sigma \sigma \sigma \sigma \sigma \end{array}$$

从左往右比较字符，直到不匹配。此时 $A$ 和 $B$ 的绿串相等。

$$\begin{array}{rl}A& =\sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \sigma \\ B& =\sigma \sigma \sigma \sigma \sigma \sigma \sigma \end{array}$$

在绿串中找出 最长的 公共前后缀。

$$\begin{array}{rl}A& =\sigma \sigma \sigma \underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \sigma \sigma \\ B& =\underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \end{array}$$

右移 $B$ 串，直到公共前后缀竖直对齐。

$$\begin{array}{rl}A=\sigma \sigma \sigma & \underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \sigma \sigma \\ B=& \underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \end{array}$$

从对齐部分的后一个字符开始，继续向右匹配，重复前面的过程。

$$\begin{array}{rl}A=\sigma \sigma \sigma & \underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \sigma \sigma \\ B=& \underset{―}{\sigma \sigma }\sigma \sigma \sigma \sigma \sigma \end{array}$$

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

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

$$\begin{array}{rl}A& =\sigma \sigma \sigma \sigma \sigma \stackrel{\stackrel{i}{\downarrow }}{\sigma }\sigma \sigma \sigma \sigma \sigma \sigma \\ B& =\sigma \sigma \sigma \sigma \sigma \underset{\underset{j}{\uparrow }}{\sigma }\sigma \end{array}$$$$\begin{array}{rl}A=\sigma \sigma \sigma \sigma \sigma \stackrel{\stackrel{i}{\downarrow }}{\sigma }& \sigma \sigma \sigma \sigma \sigma \sigma \\ B=\sigma \sigma \underset{\underset{j}{\uparrow }}{\sigma }& \sigma \sigma \sigma \sigma \end{array}$$

$pre[i]$：$B[0\cdots i]$ 的最长公共前后缀的长度。

现在假设 $pre$ 数组已经处理好了。依照刚才的思路，KMP 的主程序可以分解为以下步骤：

1. 令 $i,j$ 分别指向 $A$ 和 $B$ 的开头，即 $i=0,j=0$；
2. 如果 $A[i]=B[j]$，$i$ 和 $j$ 同时右移一位；
3. 如果 $A[i]\ne B[j]$，又分两种情况讨论：
   • $j\ne 0$ 时，绿串的公共前后缀长度为 $pre[j-1]$。那么就令 $j=pre[j-1]$；
   • $j=0$ 时，$j$ 不能再往左移。此时只能将 $i$ 右移一位。
4. 重复 2、3 两个步骤，直到匹配完成。

令指针 $i$ 和 $j$ 分别指向 $A$ 串和 $B$ 串的开头。

$$\begin{array}{rl}A& =\stackrel{\stackrel{i}{\downarrow }}{a}bababc\\ B& =\underset{\underset{j}{\uparrow }}{a}babc\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =\stackrel{\stackrel{i}{\downarrow }}{a}bababc\\ B& =\underset{\underset{j}{\uparrow }}{a}babc\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =\stackrel{\stackrel{i}{\downarrow }}{aba}babc\\ B& =\underset{\underset{j}{\uparrow }}{aba}bc\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =ab\stackrel{\stackrel{i}{\downarrow }}{a}babc\\ B& =ab\underset{\underset{j}{\uparrow }}{a}bc\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =ab\stackrel{\stackrel{i}{\downarrow }}{aba}bc\\ B& =ab\underset{\underset{j}{\uparrow }}{abc}\end{array}$$

$A[i]\ne B[j]$，令 $j=pre[j-1]=2$。这样，$A[i]$ 和 $B[j]$ 前的绿串就又匹配了。

$$\begin{array}{rl}A& =ab\underset{―}{ab}\stackrel{\stackrel{i}{\downarrow }}{a}bc\\ B& =\underset{―}{ab}ab\underset{\underset{j}{\uparrow }}{c}\end{array}$$$$\begin{array}{rl}A& =ab\underset{―}{ab}\stackrel{\stackrel{i}{\downarrow }}{a}bc\\ B& =\underset{―}{ab}\underset{\underset{j}{\uparrow }}{a}bc\end{array}$$

字符串的下标是从 $0$ 开始计算的。$j=2$ 实际上就是将 $j$ 指向 $B$ 串的第 $3$ 个字符。

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =abab\stackrel{\stackrel{i}{\downarrow }}{a}bc\\ B& =ab\underset{\underset{j}{\uparrow }}{a}bc\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =abab\stackrel{\stackrel{i}{\downarrow }}{abc}\\ B& =ab\underset{\underset{j}{\uparrow }}{abc}\end{array}$$

$A[i]=B[j]$，$i$ 和 $j$ 同时右移一位。

$$\begin{array}{rl}A& =ababab\stackrel{\stackrel{i}{\downarrow }}{c}\\ B& =abab\underset{\underset{j}{\uparrow }}{c}\end{array}$$

右移后 $j=\mathrm{length}(B)=5$，指到了 $B$ 串外面，代表匹配成功。

$$\begin{array}{rl}A& =abababc\stackrel{\stackrel{i}{\downarrow }}{b}\\ B& =ababc\underset{\underset{j}{\uparrow }}{b}\end{array}$$

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{array}{rl}B& =\stackrel{\stackrel{i}{\downarrow }}{aba}bc\\ B& =\underset{\underset{j}{\uparrow }}{a}babc\end{array}$$

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

1. 如果 $B[i]=B[j]$，那么 $pre[i]=j+1$，并将 $i$ 和 $j$ 同时右移一位；
2. 如果 $B[i]\ne B[j]$，又分两种情况讨论：
   • $j\ne 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{array}{rl}B& =ab\underset{―}{ab}\stackrel{\stackrel{i}{\downarrow }}{c}\\ B& =\underset{―}{ab}\underset{\underset{j}{\uparrow }}{a}bc\end{array}$$

预处理 $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 ++;
	}
}

模板

const int N = 1e6;
int pre[N];

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

bool kmp(string str, string substr) {
	getPre(substr);
	int i = 0, j = 0;
	while (i < str.size()) {
		if (str[i] == substr[j])
			i ++, j ++;
		else if (j)
			j = pre[j - 1];
		else i ++;
		if (j == substr.size())
            return true;
	}
    return false;
}

int main() {
	string str, substr;
	cin >> str >> substr;
	cout << kmp(str, substr);
	return 0;
}

---

1. 字符串 $s$ 左部的任意子串为 $s$ 的前缀，且 $s$ 的前缀不能是 $s$ 本身。例如 freeze 的前缀有 f，fr，fre，free，freez。 ↩︎