数据结构与算法之美（笔记19）字符串匹配：KMP算法

KMP算法基本原理

KMP算法的核心思想：我们假设主串是a，模式串是b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的过程。

我们类比BM算法，在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。

当遇到坏字符的时候，我们就要把模式串往后滑动，在滑动过程中，只要模式串和好前缀上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。这个比较过程能够更加高效。

 

KMP算法就是在试图找到一个规律，在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位。

我们只要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是k。我们把模式串一次性往后滑动j-k位，相当于，每次遇到坏字符的时候，我们就把j更新成k，i不变，然后继续比较。

 

 为了表达方便，我们把好前缀的所有后缀子串中，最长的可匹配前缀子串额那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

跟你前面的BM算法一样，KMP能否提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长匹配前缀子串的结尾字符下标。我们定义为next数组。

有了next数组，我们先把KMP算法的框架给出来：

// a是主串，n是主串的长度，b是模式串,n是模式串的长度
int kmp(char* a,int n,char* b,int m){
    int j = 0;// 模式串的字符位置
    for(int i=0;i<n;++i){// i是主串的位置
        while(a[i] != b[j] && j > 0){
            j = next[j-1] + 1;// 找到好前缀的最长可以匹配位置，+1 更新j的位置，相当于往后滑动了k个位置
        }
        if(a[i] == b[j]){
            ++j;
        }
        if(j == m){// 匹配了m-1次，找到
            return i-m+1;// 返回首个字母
        }
    }
    return -1;
}

next数组计算方法

当然，我们可以使用非常笨的方法，比如要计算下面这个模式串b的next[4]，我们就把b[0,4] 所有后缀子串，从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。很显然，这个方法效率非常低。

这里的处理非常有技巧。需要慢慢读。

我们按照下标从小到大，依次计算next数组的值。当我们要计算next[i] 的时候，前面额next [0] ，next [1]，...，next[i-1]已经计算出来了。利用已经计算出来的next值，我们是否可以快速推导出next [i] 的值？

如果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,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[0,i-1] 的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0,y] 。于是，查找b[0,i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0,y] 的最长匹配后缀子串的问题。

 

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

这里给出代码的实现：

void getNext(char* text,int size,int* next){
    next[0] = -1;// 第一个没有前缀子串
    int k = -1;// 表示最长可匹配前缀子串的下标
    for(int i=1;i<size;++i){// i代表模式串每一个前缀的长度
        while(k!=-1 && text[k+1] != text[i]){// 如果下一位不相等,在0到next(k)中找次长可匹配前缀子串，并比较下个字符，直到找到或者没有
            k = next[k];
        }
        if(text[k+1] == text[i]){
            ++k;
        }
        next[i] = k;
    }
}

int kmp(char* a,int n,char* b,int m){
    int* next = new int[m];
    getNext(b,m,next);

    int j = 0;// 模式串的字符位置
    for(int i=0;i<n;++i){// i是主串的位置
        while(a[i] != b[j] && j > 0){
            j = next[j-1] + 1;// 找到好前缀的最长可以匹配位置，+1 更新j的位置
        }
        if(a[i] == b[j]){
            ++j;
        }
        if(j == m){// 匹配了m-1次，找到
            return i-m+1;// 返回首个字母
        }
    }
    return -1;
}

KMP复杂度分析

空间复杂度很容易分析，KMP算法只需要一个额外的next数组，数组的大小跟模式串相同。所以空间复杂度是O(m)，m表示模式串的长度。

KMP算法的时间复杂度有两部分，第一步是构建next数组，第二部分才是借助next数组匹配。

计算next数组的代码中，第一层for循环中i 从 1到m-1，也就是说，内部代码执行了m-1次。我们可以找一些参照变量，i和K。i 从1开始一直增加到M，而k 并不是每次for循环都会增加，所以，k 累计增加的次数肯定小于m。而while 循环里 k = next[k] ，实际上是在减少 k 的值，k 累积都没有增加超过m ，所以while 循环里面k = next[k] 总的执行次数可不可能超过m 。因此，next 数组计算的时间复杂度是 O(m)。

第二部分也是类似的，i 从 0循环增长到 n-1 ，j的增长量不可能超过i ，所以肯定小于n 。而while 循环中的那条语句j = next[j-1] +1 ，不会让j 增长的，实际上，while循环中的这条语句也是让j 在减少，而j 总共增长的量都不会超过n ，那减少的量也不可能超过n，所以while 循环中的这句语句总的执行次数不会超过n ，所以这部分的时间复杂度是O(n)。

所以，综合两个部分，KMP算法的时间复杂度是O(n+M)。