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}$$

该绿串还有着相同的前缀1和后缀.我们管它叫做「公共前后缀」. $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 的思路已经很明朗了.

将 $A$ 串和 $B$ 串左端对齐($σ$ 表示不定字符).

$$\begin{aligned} A &= σσσσσσσσσσσσ\\ B &= σσσσσσσ \end{aligned}$$

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

$$\begin{aligned} A &= \color{green}{σσσσσ}\color{red}σ\color{black}σσσσσσ\\ B &= \color{green}{σσσσσ}\color{red}σ\color{black}σ \end{aligned}$$

在绿串中找出相同的前缀和后缀(公共前后缀).

$$\begin{aligned} A &= \color{lightgreen}{σσσ}\color{green}{\underline{σσ}}\color{black}σσσσσσσ\\ B &= \color{green}{\underline{σσ}}\color{lightgreen}{σσσ}\color{black}σσ \end{aligned}$$

右移 $B$ 串,直到前缀和后缀竖直对齐.

$$\begin{aligned} A = \color{lightgreen}{σσσ}&\color{green}{\underline{σσ}}\color{black}σσσσσσσ\\ B = \;&\color{green}{\underline{σσ}}\color{lightgreen}{σσσ}\color{black}σσ \end{aligned}$$

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

$$\begin{aligned} A = σσσ&\color{green}{\underline{σσ}}\color{goldenrod}σ\color{black}σσσσσσ\\ B = \;&\color{green}{\underline{σσ}}\color{goldenrod}σ\color{black}σσσσ \end{aligned}$$

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

指针 $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$ 右移一位.

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

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

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

$A[i]=B[i]$,$i$ 和 $j$ 同时右移一位.

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

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

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

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

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

$A[i]=B[j]$,$i$ 和 $j$ 同时右移一位.

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

此时 $j=B\;$串长度 $ =5$,指到了 $B$ 串外面,代表匹配成功.

$$\begin{aligned} A&=ab\textcolor{green}{ababc}\overset{\overset{ i}{↓}}{\color{white}{b}}\\ B&=\textcolor{green}{ababc}\underset{\underset{ j}{↑}}{\color{white}{b}} \end{aligned}$$

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 ++;
	}
}

模板 #

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↩︎