一文看懂KMP（看毛片）算法

2022-04-13 08:22:19

一文看懂KMP算法

KMP是一种模式匹配算法。常用于在一个较长的字符串中查找一个较短的字符串。通常称较长的字符串为主串，较短的待匹配的字符串为模式串。

比如给定一个主串S = ababacd，一个模式串P = abac，那么最终能够在主串中成功匹配到模式串

通常，针对某一些算法问题，我们可以首先考虑一个暴力的解法，随后通过寻找规律，来省略掉一些无效的步骤，从而完成优化。

对于字符串匹配，很容易想到的暴力解法就是使用双指针。

如主串S的长度为n，模式串P的长度为m（n > m）。定义指针i和j，i初始指向主串的第一个位置，j初始指向模式串的第一个位置。

我们先假设S中包含了P，则在[1, n]区间内（下标从1开始），一定存在一个位置i，是S匹配P的起始位置。

如S = ababcd，P = abac，根据上图，我们一眼就能看出，S中包含了P，且起始位置是3。

所以，我们只需要在[1, n]区间内枚举i，并与P比较，若以某一个i为起点，能够完整匹配P，则找到答案。

我们比较主串的S[i]和模式串的P[j]

若二者相等，则i和j都往后移动一位，继续比较S[i]和P[j]
若二者不等，则主串中当前位置为起点无法匹配

将起点往后移一位（i从2开始），继续比较

最终在i = 3为起点时，成功匹配

暴力解法写成代码如下

#include<iostream>
using namespace std;

const int N = 1e6 + 10, M = 1e5 + 10;
char s[N], p[M];

int main() {
	int n, m; // 主串S和模式串P的长度
	cin >> n >> m;
	// 读入主串S和模式串P, 下标都从1开始
	cin >> s + 1 >> p + 1;

	// 枚举 i = [1, n], 尝试匹配
	int i, j;
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= m; j++) {
			if(s[i + j - 1] != p[j]) break;
		}
		if(j == m + 1) printf("%d ", i); // 匹配成功, 打印起始坐标
	}
	return 0;
}

暴力解法i最多从1移动到n，每次尝试匹配时，j最多会移动m - 1次，所以暴力解法的时间复杂度为O(n×m)

那么KMP算法是怎么优化的呢？KMP采用了一种很巧妙的方法，比如上面的S = ababacd，P = abac，当我们进行到这一步时

发现S[i] = b与P[j] = c不匹配，但我们能不能利用一下前面已经匹配了的aba呢？答案是可以的，我们观察可以发现，已经匹配的aba，其前缀a和后缀a是相同的，我们可以不用回溯指针i，而是移动下面的模式串P

上面的操作，取决于已匹配的字符串中，前缀和后缀相等的最大长度。

比如对于字符串aba，其所有可能的前缀为{a，ab}（不包含其本身），而其所有可能的后缀为{a，ba}

取前缀集合与后缀集合的交集，结果为{a}，则对于aba，前缀和后缀相等的最大长度就是1。

再比如，对于字符串ababa，其所有可能的前缀为{a, ab, aba, abab}，其所有可能的后缀为{a, ba, aba, baba}

前缀集合与后缀集合的交集为{a, aba}，其中长度最大的是aba，所以对于ababa，前缀和后缀相等的最大长度就是3。

对于一个长度为n的字符串，存在一个最大的k（k < n），使得该字符串的前缀[1,k]和后缀[n-k+1, n]相等。当然，当不存在相等的前缀和后缀时，k为0。

这个相等的前缀与后缀有什么作用呢？

考虑如下情况，当我们匹配了一定的长度时，然后发现S[i]和P[j]不相等，此时我们可以利用前面已经匹配的部分，将模式串P一次性往右移动多个位置，而不移动指针i，那么P需要一次性移动多少呢？这就需要用到上面提到的前缀后缀相等的最大长度这个概念了

假设上图中已经匹配的绿色的部分，其前缀后缀相等的最大长度为k，如下图标为粉色的部分

很明显，我们可以将P串直接往右挪动（实际是回溯指针j，将j往左移动，移动到P串中粉色部分的最右端），使得上下的粉色部分进行对齐，然后接着继续比较S[i]和P[j]即可

由于，S和P可能在任何一个位置出现不匹配，那么我们对P的每个位置，都需要求解以该位置为终点的前缀后缀相等的最大长度，这也是求解KMP算法中最核心的next数组。

比如对于P = ababac，其next数组求解出来结果如下

下标	1	2	3	4	5	6
值	0	0	1	2	3	0

解释：

next[1] = 0，因为前缀后缀的长度必须要小于字符串本身，所以next[i]一定是小于i的，而next[1] = 0也就表示了：a这个字符串，由于不存在前缀与后缀，其前缀与后缀相等的最大长度为0
next[2] = 0，观察ab这个字符串，其可能的前缀只有一个a，可能的后缀也只有一个b，前缀集合与后缀集合的交集为空集。即，不存在相等的前缀和后缀，所以next[2]也为0
next[3] = 1，观察aba这个字符串，其前缀集合为{a, ab}，后缀集合为{a, ba}，二者的交集为{a}，所以相等的前缀后缀的长度就是1
next[4] = 2，观察abab，前缀集合为{a, ab, aba}，后缀集合为{b, ab, bab}，二者的交集为{ab}，这个相等的前缀和后缀的长度就是2
next[5] = 3，观察ababa，前缀集合为{a, ab, aba, abab}，后缀集合为{a, ba, aba, baba}，二者的交集为{a, aba}，其中最大的长度就是3
next[6] = 0，观察ababac，前缀集合为{a, ab, aba, abab, ababa}，后缀集合为{c, ac, bac, abac, babac}，二者的交集为空集，不存在相等的前缀和后缀，所以next[6]为0

为什么我们的数组下标从1开始，这是为了更方便地处理边界问题，稍后展示代码时就能明白了。

接下来，有了next数组，KMP算法就变得非常简单了，下面进行代码展示，以s表示主串，p表示模式串，s的长度为n，p的长度为m，且n > m

/*1*/	for(int i = 1, j = 0; i <= n; i++) {
/*2*/		while(j > 0 && s[i] != p[j + 1]) j = next[j];
/*3*/		if(s[i] == p[j + 1]) j++;
/*4*/		if(j == m) {
/*5*/ 	    	// 匹配成功, 返回主串的起始坐标i, 下标从1开始
/*6*/   		printf("%d ", i - m + 1); 
/*7*/   		j = next[j]; // 继续后续可能的匹配
/*8*/		}
/*9*/	}

我们的下标i从1开始，j从0开始，每次比较s[i]和p[j + 1]

第2行的含义是，当j > 0，即先前已经有部分字符串匹配上，且这次没有匹配上时，回溯j，将j置为next[j]。由于此时j指向的是p串中已匹配部分的最后一个位置，next[j]则表示以当前j为终点的字符串，其相等的前缀和后缀的最大长度，这恰好能和上面我们讲解的next数组的定义对上。然后将j置为next[j]，结合上面的图来看，就是将j放到了p串中粉色部分的最后一个位置，则下次比较时，应当比较s[i]和p[j + 1]。

这就是我们代码为什么要将j从0开始枚举，而i从1开始，保持i和j错开一位，而每次比较s[i]和p[j + 1]。

当第2行的while循环结束时，

要么是j被置为0了：这种情况就是p串需要从第一位和s串进行比较（从头开始）
要么是s[i] == p[j + 1]：这种情况就是当前位置匹配上了

第3行，若当前位置能够匹配上，则将j后移一位

第4行，若j == m，则说明p串已经匹配到最后一位了（如果当前成功匹配了s[i]和p[m]，则完成匹配，此时j + 1 = m,j = m - 1，由于进入了第3行的if块，进行了j++，所以最后j变为了m），匹配完成，打印出此时s串中匹配的起点，表示找到了一个符合条件的匹配。并将j置为next[j]（往右挪动p串），继续进行后续可能的匹配。

对于KMP的核心流程，上面的解释已经十分清楚了，然而上面的求解过程需要基于next数组，所以我们仍然需要对p串进行预处理，求出其next数组。好消息是，求解p串的next数组的过程，和上面的算法流程十分相近！

我们可以对p串自身进行上面的匹配过程！

由于next[1] = 0，所以我们从第二位开始对p串进行匹配，代码如下

	for(int i = 2, j = 0; i <= n; i++) {
        // 错开一位进行匹配, 每次匹配 i 和 j + 1 位, 第一次则匹配 2 和 1
        // 当前面有匹配上的部分时, 看看当前位是否匹配, 若不匹配, 则回溯 j 
        while(j > 0 && p[i] != p[j + 1]) j = next[j]; 
        if(p[i] == p[j + 1]) j++; // 该位匹配上了, 则 j 往后移动一位
        next[i] = j; // 当前位置的 next[i] = j
    }

开始时，i = 2, j = 0，我们仍然比较p[i]和p[j + 1]，此时若p[2] = p[1]，则j++，随后next[i] = j，

则此时next[2] = 1

更通常的，对于next[i]，如果在当前位置能够匹配上，即p[i] = p[j + 1]，则next[i] = next[i - 1] + 1

如果当前位置无法匹配上，即p[i] != p[j + 1]，则需要将j置为next[j]（由于i总是大于j的，而每次得到next数组的值时，都是通过对next[i]进行赋值完成的。所以此时next[j]一定在先前就被求解出来了），即回溯j，即右移下面的p串，随后继续比较p[i]和p[j + 1]，直到

满足p[i] = p[j + 1]，则当前next[i] = j + 1
或j回溯为0，仍然p[i] != p[j + 1]，即p[i] != p[1]，则next[i] = 0

由上面的分析可见，求解next数组，与KMP的核心算法流程是一致的。我们通过让模式串p和它自身做模式匹配，求解出其next数组，随后使用p的next数组，完成主串s和模式串p的匹配。

至此，相信你已经领略到KMP算法的设计之精巧了。下面就尝试一道算法题来结束KMP的学习吧！

Acwing - 831: KMP字符串

或者

Leetcode - 28: 实现strStr()

其中Acwing - 831这道题目的题解如下

#include<iostream>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char p[N], s[M];

int n, m;

int ne[N]; // 由于 C++ 中 next 变量已经在其他的头文件定义了, 所以这里将 next 数组命名为 ne

int main() {
    
    cin >> n >> p + 1 >> m >> s + 1; // 读入p和s时, 从下标为1的位置开始读入    
    // 先求解p串的next数组
    for(int i = 2, j = 0; i <= n; i++) {
        while(j > 0 && p[i] != p[j + 1]) j = ne[j]; // 回溯j
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    // 进行s串和p串的匹配
    for(int i = 1, j = 0; i <= m; i++) {
        while(j > 0 && s[i] != p[j + 1]) j = ne[j]; // 回溯j
        if(s[i] == p[j + 1]) j++;
        if(j == n) {
            // 匹配完成
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

参考链接：https://www.zhihu.com/question/21923021

码农公寓

一文看懂KMP算法

相关文章