深入解析 Knuth-Morris-Pratt 算法：字符串匹配的高效解决方案

kmp算法

这篇文章主要是总结一下kmp算法。所以就不写暴力遍历的逻辑了。这个算法属实是让我看了挺长时间，各种讲解博客是一点也看不进去（不是写的不详细，而是总感觉写的乱七八糟很复杂），最长公共前缀一直没理解其作用，不过反反复复的刷对应的讲解视频，卒或有所闻。

因为这个算法属实是有点抽象的，怪不得都说编程的尽头是数学，所以只是单纯的看文章中的文字可能有点痛苦，但是，don’t worry，结合代码，结合图片，多看几遍，卒或有所闻。

首先，kmp算法主要是用来判断模式串是否在文本串中出现过，如果出现过，则返回最早出现的位置的经典算法。

kmp方法的大致逻辑是通过之前判断过的信息，通过一个next数组，保存模式串里面前后最长公共子序列的长度，每次回溯，通过next数组找到前面匹配过的位置。

该算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，算法也是由这三人姓氏进行命名。

思路分析

kmp算法主要是通过一个next数组（前缀表，故也有人命名为prefix数组），这个数组主要是用来保存模式串里面前后最长公共子串（最长公共前后缀）的长度，每次回溯的时候，通过next数组找到

前面已经匹配过的位置，以此来省去大量的计算时间。

用下面代码举栗子

 A := "ab ab ab a ab ab acb"
 B := "ab ab acb"

打空格是为了方便观看，实际上字符之间没有空格

首先就是A B之间一个字符一个字符的进行逐一对照，然后，在对照至B字符串的c时，出现冲突，这个时候应当把B子串后移

不过这里和暴力遍历一样一位一位的往后移是不一样的，而是移动到可能成功的位置。

当A子串的后缀集合和B子串的前缀集合有交集的时候，把b子串往后移，才能成功匹配，

这里A子串的aba和B子串的aba相等即有交集，这里将B子串后移至j的位置。

然后问题来了，我们该如何获得j指针回溯的位置（B子串后移的长度）

我们需要在前面已经获得的信息里面，不遗漏的同时尽可能多的进行匹配。

所以我们就需要找到A子串后缀集合和B子串的前缀

集合的交集里面的最长元素。

因为A B子串的相同部分是完全一样的，所以A子串后缀集合和B子串的前缀集合的交集，我们也可以换一个说法：B子串的最长公共前后缀。

B子串的最长公共前后缀，在A B子串相同字符串的这个全集里里面的补集才能越小，即使B子串移动的最少，匹配的最多。

所以B子串的最长公共前后缀长度就是j指针回溯的位置

所以我们可以在A B子串匹配之前，通过B子串计算回溯位置，并将其存放在一个next数组中。

这里的next和B子串是形成了映射数组，存放的数据next[i]就是B[1]-B[i] 的最长公共前后缀的长度。

获取next数组

next数组有三种写法

010120

-101012（第一个赋为-1其余右移）

-10-101-1（全部减一）

减一是为了避免0位置回退到0导致死循环

接下来就分析如何一点一点的往next数组里面填充数据。

大致分为四个部分：

事先说一下：对称不是中心对称，而是中心字符块对称，比如不是abccba，而是abcabc这种对称。我刚开始也是误认为是中心对称，实则并不是这样的。

初始化

 j = 0
 ​
 next[0] = 0
 ​
 for i = 0 i < s.size i++{
 ​
 }

前后缀不相同

 j = 0
 ​
 next[0] = 0
 ​
 for i = 0 i < s.size i++{
 ​
     while j>0 && s[i] != s[j]{
     j = next[j-1]
     }
     /*因为j向前回退不是只进行一次，而是有可能进行多次回退，所以这里不能使用if判断而是应该使用while*/
 }

简单解释一下为什么前后缀不同的时候要看前一位的next数组的值 a、当当前字符的前一个字符的对称程度为0的时候，只要将当前字符与子串第一个字符进行比较。这个很好理解啊，前面都是0，说明都不对称了，如果多加了一个字符，要对称的话最多是当前的和第一个对称。比如agcta这个里面t的是0，那么后面的a的对称程度只需要看它是不是等于第一个字符a了。 b、按照这个推理，我们就可以总结一个规律，不仅前面是0，如果前面一个字符的next值是1，那么我们就把当前字符与子串第二个字符进行比较，因为前面的是1，说明前面的字符已经和第一个相等了，如果这个又与第二个相等了，说明对称程度就是2了。有两个字符对称了。比如上面agctag，倒数第二个a的next是1，说明它和第一个a对称了，接着我们就把最后一个g与第二个g比较，又相等，自然对称程度就累加了，就是2了。

前后缀相同

 j = 0
 ​
 next[0] = 0
 ​
 for i = 0 i < s.size i++{
 ​
     while j>0 && s[i] != s[j]{
     j = next[j-1]
     }
     
     if s[i] == s[j]{
          j++
         //因为这里判断出来前后缀相同，所以这里的代表着最长相等前后缀的j自然要+1
     }
 }

更新next数组的值

 j = 0
 ​
 next[0] = 0
 ​
 for i = 0 i < s.size i++{
 ​
     while j>0 && s[i] != s[j]{
     j = next[j-1]
     }
     
     if s[i] == s[j]{
          j++
         //因为这里判断出来前后缀相同，所以这里的代表着最长相等前后缀的j自然要+1
          next [i] = j
     }
 }

代码

这里是一个完整的kmp算法的代码。

 package main
 ​
 import (
     "fmt"
 )
 ​
 // kmpSearch 进行 KMP 算法的字符串匹配
 func kmpSearch(text, pattern string) {
     next := buildNext(pattern)
     n := len(text)
     m := len(pattern)
     i := 0 // text 的索引
     j := 0 // pattern 的索引
 ​
     for i < n {
         if text[i] == pattern[j] {
             i++
             j++
         }
 ​
         if j == m {
             fmt.Printf("Found pattern at index %d\n", i-j)
             j = next[j-1]
         } else if i < n && text[i] != pattern[j] {
             if j != 0 {
                 j = next[j-1]
             } else {
                 i++
             }
         }
     }
 }
 ​
 // buildNext 构建模式串的 next 数组
 func buildNext(pattern string) []int {
     m := len(pattern)
     next := make([]int, m)
     j := 0
     i := 1
 ​
     for i < m {
         if pattern[i] == pattern[j] {
             j++
             next[i] = j
             i++
         } else {
             if j != 0 {
                 j = next[j-1]
             } else {
                 next[i] = 0
                 i++
             }
         }
     }
     return next
 }
 ​
 func main() {
     text := "ABABDABACDABABCABAB"
     pattern := "ABABCABAB"
     kmpSearch(text, pattern)
 }
 ​

kmpSearch 函数：

• next := buildNext(pattern)：调用 buildNext 函数构建模式串的 next 数组。
• n := len(text) 和 m := len(pattern)：分别获取文本串和模式串的长度。
• i := 0 和 j := 0：初始化文本串和模式串的索引。
• for i < n ：遍历文本串。
  • if text[i] == pattern[j]：如果当前字符匹配，则同时移动 i 和 j。
  • if j == m：如果 j 达到模式串的长度，说明找到了一个匹配，输出匹配的起始位置，然后通过 next[j-1] 继续匹配下一个可能的子串。
  • else if i < n && text[i] != pattern[j] ：如果字符不匹配：
    • if j != 0：如果 j 不为 0，通过 next[j-1] 找到前面匹配过的位置 j。
    • else：如果 j 为 0，直接移动 i。

buildNext 函数：

• m := len(pattern)：获取模式串的长度。
• next := make([]int, m)：初始化 next 数组，其长度为模式串的长度，每个元素初始值为 0。
• j := 0 和 i := 1：初始化 j 和 i 的索引。
• for i < m ：遍历模式串。
  • if pattern[i] == pattern[j]：如果当前字符匹配，则最长公共前后缀长度 j 加 1，并将其赋值给 next[i]，然后移动 i。
  • else ：如果字符不匹配：
    • if j != 0：如果 j 不为 0，通过 next[j-1] 找到前面匹配过的位置 j。
    • else：如果 j 为 0，将 next[i] 设为 0，然后移动 i。

buildNext 函数：

• m := len(pattern)：获取模式串的长度。
• next := make([]int, m)：初始化 next 数组，其长度为模式串的长度，每个元素初始值为 0。
• j := 0 和 i := 1：初始化 j 和 i 的索引。
• for i < m ：遍历模式串。
  • if pattern[i] == pattern[j]：如果当前字符匹配，则最长公共前后缀长度 j 加 1，并将其赋值给 next[i]，然后移动 i。
  • else ：如果字符不匹配：
    • if j != 0：如果 j 不为 0，通过 next[j-1] 找到前面匹配过的位置 j。
    • else：如果 j 为 0，将 next[i] 设为 0，然后移动 i。

鸡汤

视频评论区有一句鸡汤，这里分享出来。

一个人能能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。

----KMP

参考

https://blog.csdn.net/yearn520/article/details/6729426

https://www.bilibili.com/video/BV1234y1y7pm/?spm_id_from=333.337.search-card.all.click

https://www.bilibili.com/video/BV1M5411j7Xx/?spm_id_from=333.788&vd_source=59fd7d01b725c7ff09c3a0e6221d9016