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

Bertha 。 2023-01-20 06:58 53阅读 0赞

## 一文看懂KMP算法 ##

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

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

![image-20210511104025001][]

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

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

如主串`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`，则找到答案。

![20210511104806826.png][]

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

*  若二者相等，则`i`和`j`都往后移动一位，继续比较`S[i]`和`P[j]`
    
    ![20210511105210746.png][]
 *  若二者不等，则主串中当前位置为起点无法匹配
    
    ![20210511110115663.png][]
    
    将起点往后移一位（`i`从2开始），继续比较
    
    ![20210511111508644.png][]

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

![image-20210511104025001][]

暴力解法写成代码如下

#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`，当我们进行到这一步时

![20210511110115663.png][]

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

![2021051111383584.png][]

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

比如对于字符串`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。

![20210511142130279.png][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 2][]

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

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

解释：

*  `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
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 3][]

开始时，`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字符串][Acwing - 831_ KMP]

或者

[Leetcode - 28: 实现strStr()][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][https_www.zhihu.com_question_21923021]

[image-20210511104025001]: /images/20221021/523b0723e34444b582dca643ccf25adf.png
[20210511104806826.png]: /images/20221021/055ab5f1fcd44d23ad5384ef643638c8.png
[20210511105210746.png]: /images/20221021/b978d3f6fefd440f8aa93a67ad3219fc.png
[20210511110115663.png]: /images/20221021/e7b06d6858cf4c59a5ebc45719c51382.png
[20210511111508644.png]: /images/20221021/999240c3bfe1426f8ff4b3f1ac9ded1f.png
[2021051111383584.png]: /images/20221021/d7de263a7a8f42aba47218e93e14fdee.png
[20210511142130279.png]: /images/20221021/547d601583a6498fa58ecbb46d4a54eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221021/035363d493e34394b3ef9295a47542d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/9527782ea25a4ffe8d35f5926a0b56ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 2]: /images/20221021/42a41ebf66104e278c1faf314974d656.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 3]: /images/20221021/e57e7df47b2d4b8aa3a07a27adb9de4f.png
[Acwing - 831_ KMP]: https://www.acwing.com/problem/content/description/833/
[Leetcode - 28_ _strStr]: https://leetcode-cn.com/problems/implement-strstr/
[https_www.zhihu.com_question_21923021]: https://www.zhihu.com/question/21923021