KMP算法

Soul Lv2
  2025-05-22 21:34:31 2025-05-22 21:34:31 创建   2025-05-23 22:15:29 2025-05-23 22:15:29 更新   2.2k 字  8 分钟  

今天新开一个 tag，专门用来聊一些算法，我们第一篇讲一讲相当注明的字符串匹配算法，这个算饭解决的是如下的问题：

对于任意一个字符串 s，给定另一个字符串 m，请判断 m 是否为 s 的子串，即 s 中是否包含 m，并指出 s 中出现 m 的具体位置
例如对于 abc，我们称 ab，a 等字符串为其子串

我们能想到的最简单的算法就是通过两个循环嵌套来解决问题了，我们认为这种算法的复杂度为 O（m * n），这种写法还是比较简单的，我就不具体写了，今天我们来讲另一种解决思路：KMP 算法。

KMP 算法由三位大佬共同发现，KMP 分别是三位的名字的首字母，没什么特别的含义。

在具体的介绍算法之前，我们先引入几个概念：（将字符串 s 称为文本串，m 称为模式串）

  • 前缀： 指的是一个字符串不包含最后一个字符且以该字符串的第一个字符开头的所有子串，例如对于字符串 asdf，其前缀包括 a, as, asd
  • 后缀： 指的是一个字符串不包含第一个字符且以该字符串的最后一个字符结尾的所有子串，例如对于字符串 asdf, 其后缀包括 f, df, sdf
  • 最长公共前后缀长度： 即一个字符串的前缀集与后缀集的交集中最长字符串的长度
  • 部分匹配表： 创建一个与模式串长度相同的数组 n，n[i]的值为由模式串第 0 位到第 i 位所组成的子字符串的最长公共前后缀长度，我们称 n 为该模式串的部分匹配表

然后介绍 KMP 算法的流程（假设文本串为 s，模式串为 m，已经创建了一个部分匹配表 n）：

  1. 创建两个指针 i 与 j 分别指向 s[0]与 m[0]
  2. 如果 s[0]与 m[0]相同，i 与 j 共同向后移一位
  3. 如果 s[0]与 m[0]不同，且 j=0，那么 i 向后移动一位，如果 j 不为 0，那么令 j=n[j-1], 继续进行匹配
  4. 直到 j 等于 m 的长度减 1，说明完全匹配，此时 i-j 即为模式串的一个起始点
  5. 如果需要找出全部匹配点位，那么将 j 归零继续寻找
    这里最为魔法的地方就在于第三步，这是什么诡异的操作？
    仔细想想，我们是在第 j 位发现不同的，这意味着其实文本串中的第 i-j 位到第 i-1 位与模式串中的第 0 位到第 j-1 位相同，那么如果 n[j-1]的值为 a，就一定有文本串的第 i-a 位到第 i-1 位与模式串的第 0 位到第 a-1 位相同，既然如此，我们直接从模式串的第 a 位与文本串的第 i 位开始继续比较。
    这个过程很好的利用了之前获取到的信息来进行比较。

有了上面的信息，你是否能够想出一个办法来创建一个模式串的部分匹配表？提示，创建部分匹配表的方法和上面匹配的过程非常像，我这里简单的写一个 java 版本的，你可以思考完后再看

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
30
31
32
33
34
35
36
37
38
39
40
41
42
public class KMP {  
    String s; //s是文本串 
    String p;  //p是模式串
    int[] next;  //习惯上将部分匹配表称为next
    public kmp(String s, String p){  
        this.s = s;  
        this.p = p;  
        next = new int[p.length()];  
        getNext();  
    }  
    private void getNext() {  
        int j = 0;  
        next[0] = 0;  
        for (int i = 1; i < p.length(); i++) {  
            while (j > 0 && p.charAt(j) != p.charAt(i)){  
                j = next[j - 1];  
            }  
            if (p.charAt(j) == p.charAt(i)){  
                j++;  
            }  
            next[i] = j;  
        }  
    }  
    public int kmp(){  
        int i = 0;  
        int j = 0;  
        while(i < s.length() && j < p.length()){  
            if(j == -1 || s.charAt(i) == p.charAt(j)){  
                i++;  
                j++;  
            }else{  
                j = next[j-1];  
            }  
        }  
        if(j == p.length()){  
            return i-j;  
        }  
        else{  
            return -1;  
        }  
    }  
}

有上面的基础，我相信 kmp 方法看懂一定不是什么问题，那么部分匹配表的生成过程呢，你真的明白了吗？我们可以这样理解。

  1. 第一轮循环中如果 p[0]=p[1]那么 next[1]=1 否则 next[1]=0，这一步很好理解，只有 aa，bb 这一类首两个字符完全相同的情况下才能保证前缀与后缀存在相同项
  2. 第二轮中 i 变成了 2，如果第 j 位和第 2 位相同，此时相当于第 1 位和第 2 位相同，也就是说字符串类似于 aaa，三个字符完全相同，此时最大公共前后缀长度一定为 2；如果第 j 位和第 2 位不相同进入 while 循环，令j = next[j - 1]再次比较，这同样借用了前面获得的信息，如果next[j - 1]=a，那么第 0 到第 a-1 位这一前缀与第 i-a 到第 i-1 位是相同的，比较第 a 位与第 i 位即可
  3. 如果第 a 位与第 i 位相同，那么第 0 位到第 i 位这一子串的最大公共前后缀长度一定为 a+1, 也就是 j++。而如果不相同，我们站在当前位置考虑，再次令j = next[j - 1]，就有了和第二步中基本相同的考虑。而在极端情况下，j 最终等于 0，也会退出 while 循环

不过如果你去网上搜索一下 kmp 算法的模板，一般的解法类似下面 (我随便找的)

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
30
31
32
33
34
35
36
37
38
class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++){
            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;
        }
    }
    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;
        for(int i = 0; i < haystack.length(); i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            if(j == needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
}

上面的解法简单的理解是相当于做了一个变量代换，将我给出的代码中的 j 减去 1 然后视为新的 j，你只要将这个模板中的 j 替换为 j-1 就可以再次得到我给出的版本。

最后我给出力扣的对应题目连接，你可以尝试一下（这玩意直接暴力算法也能过不过最好自己尝试着写一遍 KMP）：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

又发现一道题可以帮助理解 KMP 算法，所以我贴在这里，可以先看看
https://leetcode.cn/problems/repeated-substring-pattern/

这道题要求的是判断一个字符串是否是由某个子串重复 n 次产生的，同样，这道题我们可以直接暴力计算，直接使用两个循环逐次对比，但对于这类问题，我们可以选择直接使用 KMP 来快速求解，我先贴一段我写的版本

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
30
31
32
bool repeatedSubstringPattern(char* s) {  
    int len = strlen(s);  
    int i=0;  
    int j=1;  
    int next[len];  
    next[0]=0;  
    while(j<len) {//先把部分匹配表搞出来  
        if (s[i]==s[j]) {  
            next[j]=i+1;  
            j++;  
            i++;  
        }else {  
            if (i>0) {  
                i=next[i-1];  
            }else {  
                next[j]=0;  
                j++;  
            }  
        }  
    }  
  
    if (next[len-1]==0) {//只要是重复产生的，那么这个字符串一定存在相同的非空前后缀  
        return false;  
    }  
    int sublen = len-next[len-1];//字符串长度减去当前串的最大公共前后缀长度
    if (len%sublen==0) {//如果len是sublen的倍数，那么一定是重复产生的
        return true;  
    }  
    return false;  
  
}

那么问题来了，为什么上面只要 len 是 sunlen 的倍数就一定是重复产生的呢，我们假设一个字符串是由某个子串重复产生的，我们设这个子串为 a，那么我们假设：

最长前缀：a a a a
字符串： a a a a a
最长后缀： a a a a

我们可以直观的看到此时的 sublen 就是最小子串 a，这很好理解，如果一个字符串是由某个子串重复 n 次产生的，那么其最大前后缀必然为该子串重复 n-1 次产生；反之，

  • 标题: KMP算法
  • 作者: Soul
  • 创建于 : 2025-05-22 21:34:31
  • 更新于 : 2025-05-23 22:15:29
  • 链接: https://soulmate.org.cn/posts/2da0528d/
  • 版权声明: 本文章采用 CC BY-NC 4.0 进行许可。
目录
KMP算法