KMP子字符串匹配算法学习笔记

- 日理万妓 2022-10-10 09:46 148阅读 0赞

### 文章目录 ###

*   *  学习资源
     *  什么是KMP
     *  什么是前缀表
     *  为什么一定要用前缀表
     *  如何计算前缀表
     *  前缀表有什么问题
     *  使用next数组来匹配
     *  放码过来
     *   *  构造next数组
         *   *  一、初始化
             *  二、处理前后缀不相同的情况
             *  三、处理前后缀相同的情况
         *  使用next数组来做匹配
         *  代码总览
         *  测试代码
     *  时间复杂度分析

## 学习资源 ##

1.  [字符串：KMP是时候上场了（一文读懂系列）- 代码随想录][KMP_-]
2.  [字符串：都来看看KMP的看家本领！- 代码随想录][KMP_- 1]

## 什么是KMP ##

KMP算法是由这三位学者发明的：Knuth，Morris和Pratt，因此，用这三位学者名字的首字母组合成，来命名该算法。

KMP主要应用在字符串匹配上。KMP的主要思想是**当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了**。所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

## 什么是前缀表 ##

next数组就是一个前缀表（prefix table）。

**前缀表是用来回溯的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。**

为了清楚的了解前缀表的来历，举一个例子：

要在文本串：`aabaabaafa`中查找是否出现过一个模式串：`aabaaf`。

如动画所示：

![4d56e51d3b6888632e7b918feec077f0.gif][]

动画里，特意把 子串`aa` 标记上了，这是有原因的，大家先注意一下，后面还会说道。

可以看出，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了。

但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。

此时就要问了**前缀表是如何记录的呢？**

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，在重新匹配，此也意味着在某个字符失配时，**前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置**。（MyNote：文本串不用跳转）

那么什么是前缀表：**下表i之前（包括i）的字符串中，有多大长度的相同前缀后缀**。

（MyNote：本文“下表”的通假于“下标”。）

## 为什么一定要用前缀表 ##

前缀表那为啥就能告诉我们 上次匹配的位置，并跳过去呢？

回顾一下，刚刚匹配的过程在下表5的地方遇到不匹配，模式串是指向f，如图：

![ef383ddced3f290d592039fe019f7316.png][]

然后就找到了下表2，指向b，继续匹配，如图：

![8430602f811b50b8e28649d17b3994dd.png][]

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！

**下表5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。**

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

## 如何计算前缀表 ##

接下来就要说一说怎么计算前缀表。如图：

一、长度为前1个字符的子串`a`，最长相同前后缀的长度为0。（注意这里计算相同前后缀，不算重复的字符）

![97e6ce07772b51212ae2514a1a47c20f.png][]

二、长度为前2个字符的子串`aa`，最长相同前后缀的长度为1。

![933785bf404df03b82296c8bfcf4519d.png][]

三、长度为前3个字符的子串`aab`，最长相同前后缀的长度为0。

![245c6305e0b79463dc06239fe7ebdb7d.png][]

以此类推：

四、长度为前4个字符的子串`aaba`，最长相同前后缀的长度为1。

五、长度为前5个字符的子串`aabaa`，最长相同前后缀的长度为2。

六、长度为前6个字符的子串`aabaaf`，最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

![0ae27d480dcb07cf4a9bc4e27f31e4d8.png][]

可以看出**前缀表里的数值代表着就是：当前位置之前的子串有多大长度相同的前缀后缀**。

再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：

![在这里插入图片描述][20210629164515610.gif_pic_center]

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要看前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是2， 所有把下表移动到下表2的位置继续比配。可以再反复看一下上面的动画。

最后就在文本串中找到了和模式串匹配的子串了。

## 前缀表有什么问题 ##

来看一下刚刚求的这个前缀表有什么问题呢？

![5a1166763cad8978e44806d7f71021e9.png][]

看这个位置红框的位置，如果要找下表1 所对应 前缀表里的数值的时候，前缀表里的数值依然是1，然后就要跳到下表1的位置，如此就**形成了一个死循环**。

\*\*如何怎么避免呢，就把前缀表里的数值统一减一， 开始位置设置为-1 \*\*。 这一点对理解后面KMP代码很重要！！

改为如图所示：

![e157f8d975beca9b325b5d8112329c27.png][]

这样就避免的死循环，只不过后续取 前缀表里的数值的时候，要记得再+1，才是我们想要的值。

**最后得到的新前缀表在KMP算法里通常用一个next数组来表示。**

注意这个next数组就根据模式串求取的。

## 使用next数组来匹配 ##

有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。

注意next数组是新前缀表（旧前缀表统一减一了）。

匹配过程动画如下：

![在这里插入图片描述][20210629164656156.gif_pic_center]

## 放码过来 ##

下文统称haystack为文本串, needle为模式串。

[haystack, needle出处][haystack_ needle]。

### 构造next数组 ###

定义一个方法getNext来构建next数组，参数为一个名为next数组，和一个字符串。代码如下：

private void getNext(int[] next, String s) { }

**构造next数组其实就是计算模式串s，前缀表的过程**。主要有如下三步：

1.  初始化
2.  处理前后缀不相同的情况
3.  处理前后缀相同的情况

#### 一、初始化 ####

定义两个指针i和j：

*  j指向前缀终止位置（严格来说是终止位置减一的位置），
 *  i指向后缀终止位置（与j同理）。

（通常是先i后j，为什么这里相反，接下来看代码就清楚了。）

然后还要对next数组进行初始化赋值，如下：

int j = -1;
    next[0] = j;

*  j 初始化为 -1原因是前文说过前缀表要统一减一的操作（避免死循环得情况），所以j初始化为-1。
 *  next\[\] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j），next\[0\]初始化为j 。

#### 二、处理前后缀不相同的情况 ####

因为j初始化为-1，那么i就从1开始，进行s\[i\] 与 s\[j+1\]的比较。（这里可能一开始不适应理解，不用急。）

所以遍历模式串s的循环下表i 要从 1开始，代码如下：

for(int i = 1; i < s.length(); i++) {  // 注意i从1开始

如果 s\[i\] 与 s\[j+1\]不相同，也就是遇到 前后缀末尾不相同的情况，就要回退。

如何回退？next\[j\]就是记录着j（包括j）之前的子串的相同前后缀的长度。

那么 s\[i\] 与 s\[j+1\] 不相同，就要找 j+1前一个元素在next数组里的值（就是next\[j\]）。

所以，处理前后缀不相同的情况代码如下：

while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {  // 前后缀不相同了
    	j = next[j]; // 回退
    }

#### 三、处理前后缀相同的情况 ####

如果s\[i\] 与 s\[j + 1\] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next\[i\], 因为next\[i\]要记录相同前后缀的长度。

代码如下：

if (s.charAt(i) == s.charAt(j + 1)) {  // 找到相同的前后缀
    	j++;
    }
    next[i] = j; // 将j（前缀的长度）赋给next[i]

最后整体构建next数组的函数代码如下：

private void getNext(int[] next, String s) { 
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.length(); i++) {  // 注意i从1开始
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {  // 前后缀不相同了
            	j = next[j]; // 向前回溯
            }
            if (s.charAt(i) == s.charAt(j + 1)) {  // 找到相同的前后缀
            	j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }

代码构造next数组的逻辑流程动画如下：

![在这里插入图片描述][20210629164736233.gif_pic_center]

得到了next数组之后，就开始用它做匹配。

### 使用next数组来做匹配 ###

在文本串haystack里找是否出现过模式串needle。定义两个下表j 指向模式串起始位置，i指向文本串其实位置。

那么j初始值依然为-1，这是因为**next数组里记录的起始位置为-1**。

i就从0开始，遍历文本串，代码如下：

for (int i = 0; i < haystack.length(); i++) {  // 注意i就从0开始

接下来就是 haystack.charAt(i) 与 needle.charAt(j + 1) （因为j从-1开始的） 进行比较。

如果 haystack.charAt(i) 与 needle.charAt(j + 1) 不相同，j就要从next数组里寻找下一个匹配的位置。

代码如下：

while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {  // 不匹配
        j = next[j]; // j 寻找之前匹配的位置
    }

如果 haystack.charAt(i) 与 needle.charAt(j + 1) 相同，那么i 和 j 同时向后移动， 代码如下：

if (haystack.charAt(i) == needle.charAt(j + 1)) {  // 匹配，j和i同时向后移动 
    	j++; 
    }

如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置（从0开始），所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。

代码如下：

if (j == (needle.length() - 1) ) {  // 文本串s里出现了模式串t
        return (i - needle.length() + 1); 
    }

### 代码总览 ###

public class KMP { 
        private void getNext(int[] next, String s) { 
            int j = -1;
            next[0] = j;
            for(int i = 1; i < s.length(); i++) {  // 注意i从1开始
                while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {  // 前后缀不相同了
                    j = next[j]; // 向前回溯
                }
                if (s.charAt(i) == s.charAt(j + 1)) {  // 找到相同的前后缀
                    j++;
                }
                next[i] = j; // 将j（前缀的长度）赋给next[i]
            }
        }
        
        public int strStr(String haystack, String needle) { 
            if (needle.length() == 0) { 
                return 0;
            }
            int[] next = new int[needle.length()];
            getNext(next, needle);
            int j = -1; // // 因为next数组里记录的起始位置为-1
            for (int i = 0; i < haystack.length(); i++) {  // 注意i就从0开始
                while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {  // 不匹配
                    j = next[j]; // j 寻找之前匹配的位置
                }
                if (haystack.charAt(i) == needle.charAt(j + 1)) {  // 匹配，j和i同时向后移动 
                    j++; 
                }
                if (j == (needle.length() - 1) ) {  // 文本串s里出现了模式串t
                    return (i - needle.length() + 1); 
                }
            }
            return -1;
        }
    }

### 测试代码 ###

import static org.junit.Assert.*;
    
    import org.junit.Test;
    
    public class KMPTest { 
    
    	@Test
    	public void test() { 
    		KMP k = new KMP();
    		
    		assertEquals(2, k.strStr("hello", "ll"));
    		assertEquals(-1, k.strStr("aaaaa", "bba"));
    		assertEquals(3, k.strStr("aabaabaafa", "aabaaf"));
    	}
    
    }

## 时间复杂度分析 ##

假设文本串长度为n，模式串长度为m。因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，但之前还要单独生成next数组，时间复杂度是O(m)，所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n \* m)，所以**KMP在字符串匹配中极大的提高的搜索的效率**。

[KMP_-]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484428&idx=1&sn=c0e5573f5fe3b438dbe75f93f3f164fa&scene=21#wechat_redirect
[KMP_- 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484438&idx=1&sn=52cd12bec41d3b150d9e2651e1df0418&scene=21#wechat_redirect
[4d56e51d3b6888632e7b918feec077f0.gif]: /images/20221005/f28fccb47ddb489bac2deb9e9b000c68.png
[ef383ddced3f290d592039fe019f7316.png]: /images/20221005/ae56430af9ad4d41bd81495e019e8612.png
[8430602f811b50b8e28649d17b3994dd.png]: /images/20221005/0a615338dbda427a856b4cf2bf2fc0e6.png
[97e6ce07772b51212ae2514a1a47c20f.png]: /images/20221005/6470d30e41614f29818133c48465cb0a.png
[933785bf404df03b82296c8bfcf4519d.png]: /images/20221005/e3125a3968ac430fb8c896ca1f89add9.png
[245c6305e0b79463dc06239fe7ebdb7d.png]: /images/20221005/a11d16532d764dacbfcc2d3fe9eda3af.png
[0ae27d480dcb07cf4a9bc4e27f31e4d8.png]: /images/20221005/d6e7e50e63e84d4789ed44cbff63cdfc.png
[20210629164515610.gif_pic_center]: /images/20221005/68b929512e164a4aa768b3dae64658e2.png
[5a1166763cad8978e44806d7f71021e9.png]: /images/20221005/eb78a3e0243344fd8de1b299c5f91bc9.png
[e157f8d975beca9b325b5d8112329c27.png]: /images/20221005/fbef6b8e6a7840dc85fd3cdaf1704115.png
[20210629164656156.gif_pic_center]: /images/20221005/781d1f3074aa4ba2bbacb4801bdd50f9.png
[haystack_ needle]: https://leetcode.com/problems/implement-strstr/
[20210629164736233.gif_pic_center]: /images/20221005/d2f5a69607b641a9a898ed08fab23f44.png