KMP算法-字符串匹配(浅显易懂）_字符串匹配算法kmp

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

本篇将以如下顺序来讲解KMP，

• 什么是KMP
• KMP有什么用
• 什么是前缀表
• 为什么一定要用前缀表
• 如何计算前缀表
• 前缀表与next数组
• 使用next数组来匹配
• 时间复杂度分析
• 构造next数组
• 使用next数组来做匹配
• 前缀表统一减一 C++代码实现
• 前缀表（不减一）C++实现
• 总结

本篇内容参考和总结了
代码随想录:https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
知乎文章:https://www.zhihu.com/question/21923021

什么是KMP

说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。

因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP

KMP有什么用

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

其实KMP的代码不好理解，一些同学甚至直接把KMP代码的模板背下来。

没有彻底搞懂，懵懵懂懂就把代码背下来太容易忘了。

不仅面试的时候可能写不出来，如果面试官问：next数组里的数字表示的是什么，为什么这么表示？

估计大多数候选人都是懵逼的。

下面就带大家把KMP的精髓，next数组弄清楚。

什么是前缀表

写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？

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

前缀表有什么作用呢？

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

• 其实就是求不匹配字符前的字符串的 最长相等的前后缀问题

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

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

请记住文本串和模式串的作用，对于理解下文很重要，要不然容易看懵。所以说三遍：

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

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

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

如动画所示：

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

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

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

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

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

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

最长公共前后缀

文章中字符串的

• 前缀** 是指不包含最后一个字符的所有以第一个字符开头的连续子串**。
• 后缀** 是指不包含第一个字符的所有以最后一个字符结尾的连续子串**。
  • 注意：aabaa的前缀和后缀都是从左往右数

正确理解什么是前缀什么是后缀很重要!

那么网上清一色都说 “kmp 最长公共前后缀” 又是什么回事呢？

我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 更准确一些。

因为前缀表要求的就是相同前后缀的长度。

而最长公共前后缀里面的“公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…。

为什么一定要用前缀表

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

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

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

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

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

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

很多介绍KMP的文章或者视频并没有把为什么要用前缀表？这个问题说清楚，而是直接默认使用前缀表。

如何计算前缀表

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

如图：

长度为前1个字符的子串a，最长相同前后缀的长度为0。

注意

• 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
• 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

以此类推： 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。

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

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

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

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

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

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

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

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

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

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

前缀表与next数组

很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

为什么这么做呢，其实也是很多文章视频没有解释清楚的地方。

其实这并不涉及到KMP的原理，而是具体实现，next数组即可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

后面我会提供两种不同的实现代码，大家就明白了。

使用next数组来匹配

以下我们以前缀表统一减一之后的next数组来做演示。

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

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

匹配过程动画如下：

时间复杂度分析

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

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

为了和力扣题目28.实现strStr保持一致，方便大家理解，以下文章统称haystack为文本串, needle为模式串。

都知道使用KMP算法，一定要构造next数组。

构造next数组

我们定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。 代码如下：

public static int[] getNext(String s1)
1

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

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

接下来我们参考代码详解一下。

首先理解该表中next[i] 表示的含义
- next[i] : 字符串s 从 0 到 i 截取得字符串 l (前后包含)，其表示字符串 l 前缀和后缀相同部分最长值
- 举例 aabaaf 的next[1] 为0 即aa 前后缀相同时的最大长度为1
- 前缀为a
- 后缀为a

next 数组的使用

其实next数组也分为两种一种是上图表格所示，另一种是右移减一

• 上图所示的next数组:当前指针i 指向的字符与匹配字符的指针 j 指向的字符不符时，指针i从next[i-1] 的位置继续指针j开始匹配

 public static int[] getNext(String s1){
        char[] chars = s1.toCharArray();
        int[] next=new int[s1.length()];
        //初始化 j从零开始 i从1开始
        // 其中 j 表示前缀的指针
        //     如果当前 两个指针指向的数值相同，则 j+1 表示next[i]
        // 其中 i 表示后缀的指针
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < s1.length(); i++) {
            //情况一 如果两个指针指向的数值相同
            if(chars[j]==chars[i]){
                next[i] = j + 1;
                j++;
            }
            //情况二 如果两个指针指向的数值不同 j重新指向初始位置 next[i]=0;
            else {
                next[i] = 0;
                j = 0;
            }

        }
        return next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1. 初始化：

定义两个指针i和j
- j指向前缀起始位置
- i指向后缀起始位置

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

        //初始化 j从零开始 i从1开始
        // 其中 j 表示前缀的指针
        //     如果当前 两个指针指向的数值相同，则 j+1 表示next[i]
        // 其中 i 表示后缀的指针
        next[0] = 0;
        int j = 0;
1
2
3
4
5
6

`next[0]` :初始化为0，因为它没有前后缀啊

- 前缀 是指不包含最后一个字符的所有以第一个字符开头的连续子串。
- 后缀 是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
1
2
3
4

next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）

所以初始化next[0] = 0 。

2. 处理前后缀相同的情况

因为j初始化为0，那么i就从1开始，进行s[i] 与 s[j]的比较。

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

for (int i = 1; i < s.size(); i++) {
1

如果s[i] 与s[j]指向的字符相同，那么next[i]=j+1

j+1 代表前缀的长度, 而前缀的长度就是next 数组的值

同时指针j 移动

代码如下：

//情况一 如果两个指针指向的数值相同
            if(chars[j]==chars[i]){
                next[i] = j + 1;
                j++;
            }
1
2
3
4
5

3. 处理前后缀不相同的情况

目标我们需要求得P[0]…P[x]中的最长相同的前缀后缀，但是我们遇到了不相同的情况

如图所示: 当前P[now]≠P[x]

因为决定这个 最长相同的前缀后缀 是前缀和后缀的长度

现在我们观察子串A和子串B，这两个子串完全一样，我们要取得P[0]…P[x]中的最长相同的前缀后缀的问题就转换为

• 我们要取到最大的子串A的前缀和子串B的后缀相同

其实转换成了子串A的最大前后缀问题，即为 now = P[now-1]=2

现在now指针指向C为2，然后接着比较P[now]与P[X]

如果仍旧不相等重复上述操作取now，直到now指向0

最后有两种结果

• 匹配到P[now]==P[X]，接着往匹配
• now最后为0，所以next[i]=0,i++
• 这里的now对应代码中的j
• 这里的X对应代码中的i

//情况二 如果两个指针指向的数值不同
            else {
                while(j!=0 && chars[j]!=chars[i]){
                    j=next[j-1];
                }
                if(j==0){
                    next[i]=0;
                    i++;
                }
            }

1
2
3
4
5
6
7
8
9
10
11

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

 public static int[] getNext(String s1){
        char[] chars = s1.toCharArray();
        int[] next=new int[s1.length()];
        //初始化 j从零开始 i从1开始
        // 其中 j 表示前缀的指针
        //     如果当前 两个指针指向的数值相同，则 j+1 表示next[i]
        // 其中 i 表示后缀的指针
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < s1.length(); i++) {
            //情况一 如果两个指针指向的数值相同
            if(chars[j]==chars[i]){
                next[i] = j + 1;
                j++;
            }
            //情况二 如果两个指针指向的数值不同
            else {
                while(j!=0 && chars[j]!=chars[i]){
                    j=next[j-1];
                }
                if(j==0){
                    next[i]=0;
                    i++;
                }
            }

        }
        return next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

得到了next数组之后，就要用这个来做匹配了

next数组的使用

其实上面也说了如何使用

next数组的使用

• 设置两个指针i，j分别指向匹配字符串ss和原字符串s
• 获取原字符串s的next数组
• 当i<ss.length时
  • 如果字符串匹配
    • 两个指针一起移动
    • 移动后如果j的值等于s.length，即已经匹配到了字符串，返回i-ss.length
    • continue
  • 如果字符串不匹配
    • 首先判断j是否等于0，防止第一个字符不匹配无限循环，如果等于0，i++
    • j不等于0，这时需要利用next数组重新定位j的位置，即求出j前方的字符串的最长前后缀，所以j=next[j-1]

public static int strStr(String haystack, String needle) {
        if(needle.equals("")) return 0;
        char[] a = haystack.toCharArray();
        char[] b = needle.toCharArray();
        int[] next = getNext(needle);
        int j=0;
        int i=0;
        while(i<haystack.length()) {
                // 如果字符匹配
                if(b[j] == a[i]) {
                    j++;
                    i++;
                    if(j==needle.length()) return i-needle.length();
                    continue;
                }
                // 如果字符不匹配
                if(b[j] != a[i]) {
                    // 防止第一个字符不匹配无限循环
                    if(j==0) {
                        i++;
                        continue;
                    }
                    // 需要重新定位 j 指向的位置
                    j = next[j-1];
                }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28