字符串匹配——KMP算法

目录

KMP（Knuth Morris Pratt）

KMP算法复杂度分析

字符串匹配中除了简单的BF（Brute Force）、RK（Rabin-Karp）算法，还有更高效、较难理解的

BM（Boyer-Moore）和KMP（Knuth Morris Pratt）算法。这次来聊聊KMP（Knuth Morris Pratt）算法。

KMP（Knuth Morris Pratt）

KMP算法是根据三位作者（D.E.Knuth，J.H.Morris和V.R.Pratt）的名字来命名的，算法的全称是Knuth Morris Pratt算法，简称为KMP算法。

KMP算法的核心思想和BM（Boyer-Moore）非常相近。(BM算法简介)

为了表述起来方便，好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

需要提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标，叫做next数组。

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

模式串：a b a b a b e a b

在next数组的帮助下，KMP算法就方便实现了。假设next数组已计算好，KMP的算法框架大致如下：

// a和b表示主串和模式串，n和m分表表示主串和模式串的长度
public static int kmp(char[] a, int n, char[] b, int m) {
    int[] next = getNextArr[b, m];// 通过模式串获取next数组
    int j = 0;
    for(int i = 0; i < n; i++) {
        while(j > 0 && a[i] != b[j]) { // 一直找到a[i] = b[j]
            j= next[j - 1] + 1; 
        }
        if (a[i] == b[j]) { 
            ++j;
        }
        if (j == m) { // 找到匹配的串了
            return i - m + 1;
        }
    }
    return -1;
}

接下来需要解决的是getNextArr了。

我们按照下标从小到大，依次计算next数组的值。当我们要计算next[i]的时候，前面的next[0]，next[1]，……，next[i-1]应该已经计算出来了。 如果next[i-1]=k-1，也就是说，子串b[0, k-1]是b[0, i-1]的最长可匹配前缀子串。如果子串b[0, k-1]的下一个字符b[k]，与b[0, i-1]的下一个字符b[i]匹配，那子串b[0, k]就是b[0, i]的最长可匹配前缀子串。所以，next[i]等于k。但是，如果b[0, k-1]的下一字符b[k]跟b[0, i-1]的下一个字符b[i]不相等呢？这个时候就不能简单地通 过next[i-1]得到next[i]了。

我们假设b[0, i]的最长可匹配后缀子串是b[r, i]。如果我们把最后一个字符去掉，那b[r, i-1]肯定是b[0, i-1]的可匹配后缀子串，但不一定是最长可匹配后缀子串。所 以，既然b[0, i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于b[i]，那么我们就可以考察b[0, i-1]的次长可匹配后缀子串b[x, i-1]对应的可匹配前缀子串b[0, i-1-x]的下一个字符b[i-x]是否等于b[i]。如果等于，那b[x, i]就是b[0, i]的最长可匹配后缀子串。

次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串b[0, y]。于是，查找b[0, i-1]的次长可匹配后缀子串，这个问题就变成，查找b[0, y]的最长匹配后缀子串的问题了。

按照这个思路，我们可以考察完所有的b[0, i-1]的可匹配后缀子串b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于b[i]，那这个b[y, i]就是b[0, i]的最长可匹配后缀子串。

// b表示模式串，m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
    int[] next = new int[m];
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < m; ++i) {
        while (k != -1 && b[k + 1] != b[i]) {
            k = next[k];
        }
        if (b[k + 1] == b[i]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

KMP算法复杂度分析

KMP算法包含两部分，第一部分是构建next数组，时间复杂度主要取决于while循环里面k=next[k]总的执行次数，这部分时间复杂度是O(m)。第二部分才是借助next数组匹配，取决于while循环中的这条语句总的执行次数也不会超过n，所以这部分的时间复杂度是O(n)。

贴个carl的讲解连供诸君参考

• 视频讲解版：帮你把KMP算法学个通透！（理论篇）(opens new window)
• 视频讲解版：帮你把KMP算法学个通透！（求next数组代码篇）(opens new window)
• 文字讲解版：KMP算法