数据结构串 KMP 模式匹配详解通俗易懂

KMP 模式匹配详解通俗易懂KMP 模式匹配是解决字符串匹配的问题一、原始的字符串暴力匹配要点：子串的第一个字符匹配成功主串的字符后就依次匹配子串后面的字符，直到子串匹配结束代码：public static int forceMatch(char[] mainString,char[] pattern){int i = 0;int j = 0;//回溯的指针int k = 0;while (i &

邓嘉文Jarvan

3480人浏览 · 2021-01-02 13:05:40

邓嘉文Jarvan · 2021-01-02 13:05:40 发布

KMP 模式匹配详解通俗易懂

KMP 模式匹配是解决字符串匹配的问题

一、原始的字符串暴力匹配

要点：子串的第一个字符匹配成功主串的字符后就依次匹配子串后面的字符，直到子串匹配结束

代码：

public static int forceMatch(char[] mainString,char[] pattern){
  int i = 0;
  int j = 0;
  //回溯的指针
  int k = 0;
  while (i < mainString.length && j < pattern.length){
    //继续匹配模式串后继字符
    if (mainString[i] == pattern[j]){
      i ++;
      j ++;
    }//模式串右移 回溯主串地址
    else {
      k++;
      i = k;
      j = 0;
    }
  }
  if (j == pattern.length){
    return k;
  }
  return -1;
}

下面是主串 “abcdefgab” 子串 “abcdex” 的原始暴力匹配流程

暴力匹配存在的问题：

每次匹配失败都可以得出 2 个结论：

当前字符匹配失败（比如步骤 1 的「红色线」）
当前匹配字符前面的字符匹配成功（比如步骤 1 的「绿色线」）

暴力匹配并没有有效利用第二条结论。

KMP 模式匹配算法利用第二条结论，是一个效率极高 O(n+m) 的字符串匹配算法

二、KMP 模式匹配算法

2.1 减少主串指针「回溯」

什么是「回溯」:

还是刚刚例子：

在第 1 步中，主串的指针 i,j 一步一步匹配增加到了 i = 5,j =5
第 2 步中，因为第一步匹配失败 i,j 都「回溯」到了 i = 1,j = 0

指针增加然后又减少，这就是「回溯」

如何减少「回溯」：

还是刚刚的例子：

上图的步骤 1 主串 “abcdefgab” 匹配了子串前面的 5 个字符 “abcde”（看「绿色线」）
子串 “abcdex” 的首字母 “a” 和后面的 “bcdex” 都不相等。
意味着子串上的首字符 “a” 必然不可能再与主串上的前面 5 个字符 “bcde” 匹配（看绿色线）

按照我们人类的思维，上图的 2、3、4、5 步都是多余的。（这个人类的思维也是理解 KMP 算法的关键）

如果我们减少了 2、3、4、5 步骤就「减少了回溯」

减少主串指针「回溯」：

上面的例子当我们减少完 2、3、4、5 步骤之后。

只剩下 1 和 6 步骤：

我们发现主串指针 i 没有再发生回溯了，只有指针子串指针 j 回溯到了 j = 0。

子串指针 j 回溯的位置也是有讲究的（能回溯到 0 的原因是：子串 “abcdex” 的首字母 “a” 和后面的 “bcdex” 都不相等）

子串回溯的位置取决于 匹配字符前面的字符串的 「最长前后缀相同长度」

2.1 最长前后缀相同长度

定义：

前缀：组成包含第一个字符，不包含最后一个字符
后缀：组成包含最后一个字符，不包含第一个字符
最长前后缀长度：：前缀后缀相等最长的元素

（前缀后缀补不能为同一个元素，比如：在 a 中，前缀后缀不能同时为 a，这个「最长前后缀长度」为 0）

举个例子：

abcde 中

前缀有：a、ab、abc、abcd

后缀有：e、de、cde、bcde

最长前后缀相同长度：为 0

子串回溯的位置取决于 匹配字符前面的字符串的 「最长前后缀相同长度」

所以子串指针 j 回溯到 j = 0

求「最长前后缀相同长度」习题（建议自己推导一遍）：

有人就会问，如果子串后面也含有首字符 “a” 的字符怎么办呢？

（1）例子 1

aaaaa

前缀有：a、aa、aaa、aaaa

后缀有：a、aa、aaa、aaaa

最长的前后缀相同长度：4

子串回溯的位置取决于 匹配字符前面的字符串的 「最长前后缀相同长度」

所以子串指针 j 回溯到 j = 4

（2）例子 2

ababa

前缀有：a、ab、aba、abab

后缀有：a、ba、aba、baba

最长的前后缀相同长度：3

子串回溯的位置取决于 匹配字符前面的字符串的 「最长前后缀相同长度」

所以子串指针 j 回溯到 j = 3

2.3 `next[]` 数组

我们通过「最长前后缀相同长度」求出匹配 单个匹配字符的回溯的位置

next[] 数组就是记录 子串所以字符的回溯位置

子串回溯位置 next[j] 公式如下:

next[0] = -1，当 j = 0 时候

next[j] = 匹配字符前面的字符串的「最长前后缀相同长度」，当 j > 0 时

（1）例子 1

abcdex

j = 0 , 匹配字符前面的字符串为 null，所以 next[0] = -1（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）

j = 1 , 匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」next[1] = 0（这个点其实也是固定的）

j = 2 , 匹配字符前面的字符串为 ab ，所以「最长前后缀相同长度」next[2] = 0

j = 3 , 匹配字符前面的字符串为 abc ，所以「最长前后缀相同长度」next[3] = 0

j = 4 , 匹配字符前面的字符串为 abcd ，所以「最长前后缀相同长度」next[4] = 0

j = 5 , 匹配字符前面的字符串为 abcde ，所以「最长前后缀相同长度」next[5] = 0

综上 next[] = [-1,0,0,0,0,0]

（2）例子 2

aaaaax

j = 0 , 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」 next[0] = -1（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）

j = 1 , 匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」next[1] = 0（这个点其实也是固定的）

j = 2 , 匹配字符前面的字符串为 aa ，所以「最长前后缀相同长度」next[2] = 1

j = 3 , 匹配字符前面的字符串为 aaa ，所以「最长前后缀相同长度」next[3] = 2

j = 4 , 匹配字符前面的字符串为 aaaa ，所以「最长前后缀相同长度」next[4] = 3

j = 5 , 匹配字符前面的字符串为 aaaaa ，所以「最长前后缀相同长度」next[5] = 4

综上 next[] = [-1,0,1,2,3,4]

（3）例子 3

ababax

j = 0 , 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」 next[0] = -1（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）

j = 1 , 匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」next[1] = 0（这个点其实也是固定的）

j = 2 , 匹配字符前面的字符串为 ab ，所以「最长前后缀相同长度」next[2] = 0

j = 3 , 匹配字符前面的字符串为 aba ，所以「最长前后缀相同长度」next[3] = 1

j = 4 , 匹配字符前面的字符串为 abab ，所以「最长前后缀相同长度」next[4] = 2

j = 5 , 匹配字符前面的字符串为 ababa ，所以「最长前后缀相同长度」next[5] = 3

综上 next[] = [-1,0,0,1,2,3]

2.4 通过 next[] 实现的 KMP 算法代码

代码

public static int kmp(char[] mainString, char[] pattern) {
    int[] next = getNext(pattern);
    //KMP 模式匹配 i 指针不回溯，j 指针回溯到 next[j] 的位置
    int i = 0;
    int j = 0;
    while (i < mainString.length && j < pattern.length) {
        //继续匹配模式串后面的字符
        if (j == -1 || mainString[i] == pattern[j]) {
            i++;
            j++;
        }
        //j 指针回溯到 next[j] 的位置
        else {
            j = next[j];
        }
    }
    if (j == pattern.length) {
        return i - j;
    }
    return -1;
}
/**
 * 求 next[] ,利用 next[j] 求 next[j+1] 十分巧妙
 */
private static int[] getNext(char[] pattern) {
    int[] next = new int[pattern.length];
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < pattern.length - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

测试


public static void main(String[] args) {
  char[] main = "goo432fsdaglxgoogle".toCharArray();
  char[] pattern = "google".toCharArray();
  int[] next = new int[]{-1, 0, 0, 0, 1, 0};
  System.out.println("====KMP KMP返回匹配的起始位置 ====");
  System.out.println(kmp(main, pattern));
}

输出

====KMP KMP返回匹配的起始位置 ====
13

三、算法优化改进

3.1 问题

KMP 算法还是存在缺陷比如上面的「例子 2」主串为 “aaaaabgab” 从串为 “aaaaax”

（1）求出 next[]

同理「例子 2」

aaaaax

j = 0 , 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」 next[0] = -1（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）

j = 1 , 匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」next[1] = 0（这个点其实也是固定的）

j = 2 , 匹配字符前面的字符串为 aa ，所以「最长前后缀相同长度」next[2] = 1

j = 3 , 匹配字符前面的字符串为 aaa ，所以「最长前后缀相同长度」next[3] = 2

j = 4 , 匹配字符前面的字符串为 aaaa ，所以「最长前后缀相同长度」next[4] = 3

j = 5 , 匹配字符前面的字符串为 aaaaa ，所以「最长前后缀相同长度」next[5] = 4

综上 next[] = [-1,0,1,2,3,4]

（2）通过 next[] KMP 部分流程如下

通过人类的思维我们可以发现：

子串 “aaaaax” 的前 4 个字符 a 与第 5 个字符 a 是相等的
在 2 步骤中，第 5 个字符 a 匹配失败，意味着前面 4 个 a 必然匹配失败。
所以 3、4、5、6 步骤是多余的，因为 后面的 a 已经不匹配了，前面的 a 也必然不能匹配

3.2 算法

下面参考子串：“aaaaax”

next[] = [-1,0,1,2,3,4]

问题的关键是：后面的第 a 已经不匹配了，前面的 a 也必然不能匹配

所以：

next[0] = -1，固定值
next[1] = next[0] = -1，将相同字符 next[1] 的值，等于给他前面的相同的字符 next[0]
next[2] = next[1] = -1，将相同字符 next[2] 的值，等于给他前面的相同的字符 next[1]
next[3] = next[2] = -1，将相同字符 next[3] 的值，等于他前面的相同的字符 next[2]
next[4] = next[3] = -1，将相同字符 next[4] 的值，等于他前面的相同的字符 next[3]
第五个字符和前面的不相等，next[5] = 4

所以我们只需要在前面求 next[] 数组的地方添加一个判断

private static int[] getNextVal(char[] pattern) {
    int[] next = new int[pattern.length];
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < pattern.length - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            k++;
            j++;
            //这里添加判断
            if (pattern[j] == pattern[k]){
                //后面的字符不匹配了前面的也必然不匹配
                next[j] = next[k];
            }else {
                next[j] = k;
            }

        } else {
            k = next[k];
        }
    }
    return next;
}

对比之前求 next[]：

private static int[] getNext(char[] pattern) {
    int[] next = new int[pattern.length];
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < pattern.length - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}