侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

字符串匹配算法之 KMP 算法

kaixindeken
2021-04-21 / 0 评论 / 0 点赞 / 85 阅读 / 2,118 字

KMP 算法可以说是字符串匹配算法中最知名的算法了,KMP 算法是根据三位作者(D.E.Knuth,J.H.Morris 和 V.R.Pratt)的名字来命名的,算法的全称是 Knuth Morris Pratt 算法,简称为 KMP 算法。

KMP 算法的核心思想

假设主串是 a,模式串是 b。在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,我们希望找到一些规律,可以将模式串往后多滑动几位,跳过那些肯定不会匹配的情况,从而避免 BF 算法这种暴力匹配,提高算法性能。下面我们来探讨下这个规律如何找到。

参考下面个主串和模式串的匹配,当模式串移动到当前位置,比对到最后一个字符 D 时,发现与主串不匹配,如果按照 BF 算法,就是把模式串往后移一位,再逐个比较,这样做固然可以,但是效率很差:

1.jpeg

一个基本事实是,当 D 与主串不匹配时,我们已知前面的主串序列是 ABCDA,如果把模式串往后移一位肯定和主串不匹配,我们可不可以直接把模式串移到下一个可能和 A 匹配的主串位置?

实际上,KMP 算法正是基于这一理念,设法利用这个已知信息,不把模式串移到已经比较过的位置,继续把它向后移,这样综合下来就极大提高了搜索匹配效率。

怎么找到这个规律,确定把模式串往后移多少位呢?在模式串和主串匹配的过程中,我们把不能匹配的那个字符仍然叫作「坏字符」,把已经匹配的那段字符串叫作「好前缀」:

1.jpeg

在模式串和主串匹配的过程中,当遇到坏字符后,对于已经比对过的好前缀,我们只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀的前缀子串匹配的下标位置,然后将模式串后移到该位置即可。

这里,我们要解释几个概念:

  • 后缀子串:以某个字符串最后一个字符为尾字符的子串(不包含字符串自身),比如上面的 ababa,后缀子串为 baba、aba、ba、a;
  • 前缀子串:以某个字符串第一个字符为首字符的子串(不包含字符串自身),还是以 ababa 为例,前缀子串为 a、aba、abab;
  • 最长可匹配后缀子串:后缀子串与前缀子串最长可匹配子串,也可叫做共有子串,以 ababa 为例,自然是 aba 了,长度为 3;
  • 最长可匹配前缀子串:与上面定义相对,即前缀子串与后缀子串最长可匹配子串。最长可匹配前缀子串和最长可匹配后缀子串肯定是一样的。

假设坏字符所在位置是 j,最长可匹配后缀子串长度为 k,则模式串需要后移的位数为 j-k。每当我们遇到坏字符,就将模式串后移 j-k 位,直到模式串与对应主串字符完全匹配;如果移到最后还是不匹配,则返回 -1。这就是 KMP 算法的核心思想。

KMP 算法的实现

了解了核心思想,接下来,就可以考虑如何实现 KMP 算法了,实现 KMP 算法最核心的部分是构建一个用来存储模式串中每个前缀子串(这些前缀都有可能是好前缀)最长可匹配前缀子串的结尾字符下标数组,我们把这个数组叫做 next 数组,对于上面 ababacd 这个模式串而言,对应的 next 数组如下:

1.jpeg

其中,数组的下标是前缀子串结尾字符下标,数组的值是这个前缀的最长可匹配前缀子串的结尾字符下标。

有了这个 next 数组,我们就可以实现 KMP 匹配算法的核心代码了:

int kmp(char* a, int n, char* b, int m){
    int* next = generateNext(b, m);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && a[i] != b[j]){
            j = next[j - 1] + 1;
        }
        if (a[i] == b[j]){
            j ++;
        }
        if (j == m){
            return n - m + 1;
        }
    }
    return -1;
}

接下来就是如何生成 next 数组了,这一步是最难的,我们现在可以参考上面 next 数组生成原理通过循环比对前缀子串和后缀子串的方式去理解,毕竟我们在实际开发中不太可能自己去实现 KMP 算法,了解原理即可,以后讲到动态规划,会用动态规划来实现它。这里就不再深入探究了。

0

评论区