字符串的KMP算法详解及C/C++代码实现

1. 原由

紧接上文，我们知道了暴力匹配的算法在时间运行上的缺陷，假设字符串T的长度为n，字符串P的长度为m，则整个算法的时间复杂度为O( n * m )，而对于一个复杂的现实情况而言 n >> m >> 2 （即n远远大于m，m远远大于常数），这样的计算计算机的负担很重。

请思考一个暴力匹配的情况：

给定一个主字符串

T = “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)

同时给定模式串 P = “AAAAAB”（6位）

试问搜索的情况，很显然，暴力搜索对于每一次搜索，都要搜索到最后一个字符才能进行下一轮的搜索，因此进行的计算近似可以理解为：O(47 * 6) ，对于这样很少的数据已经有很高的计算量了。

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作， KMP算法与前文的暴力匹配算法，核心的区别就是没有不匹配的回溯，而是根据整个字符串的情况进行一次位移，这样大大减少了回溯产生的缺陷，KMP算法的时间复杂度可以优化到 O( n + m)级别，是二次优化到线性的程度。

2.构造next表(以-1开头)

对于模式串P而言，我们需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后缀，并且求这个最大的完全相等的前后缀，如一个模式串”ABCABDE”对于第倒数第二位字符而言，其符合情况的前后缀就是”AB”，而最后一位则没有完全相等的前后缀。

PS：何为前后缀：如一个字符串”ABCD”,其前缀有可能为”A”“AB”“ABC”(即除去本身的全部字符)，同理，则后缀可能为：”D””CD””BCD”

我们需要求的就是每一个字符其相对应的最大前后缀数，这样与模式串P一一对应的表称之为next表。

因此”ABCABDE”的next表为：-1 0 0 0 1 2 0 （字符用空格隔开）

那么我们该如何实现代码呢？

对于每一个当前需要判断的字符而言，在构造next表时，应该向前进行比对，以上一个已经判断的情况为基础（初始值赋-1，部分教程中初始值赋0，两者没有实质区别），后缀如果+1位置的字符与前缀+1位置的字符相等，则next[i]就是next[i-1]+1，而如果不相等，则说明无法匹配，则next[i]=0。

3. KMP实现

与暴力匹配极其相似，利用while循环的条件控制， 进行匹配失败时，只需要将失败的模式串P的索引指向next表中对应的数值即可，其余匹配照旧线性执行即可。

4. 实现代码（仅作参考）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
int *buildNext(char *P){
    int m = strlen(P) , j=0;
    int * N = new int[m];
    int t = N[0] = -1;
    while( j < m-1 ){
        if( 0 > t || P[j] == P[t] ){
            N[++j] = ++t;
        }
        else{
            t = N[t];
        }
    }
    return N;
}
 
int KMP(char T[],char P[]){ //T--主串,P--模式串
    int *next = buildNext(P);   //构造NEXT表
    int n = strlen(T) , i=0;
    int m = strlen(P) , j=0;
    while( j<m && i<n ){
        if( j<0 || T[i]==P[j] ){
            i++;
            j++;
        }else{
            j = next[j];
        }
        
    }
    delete []next;
    return i-j;
}
 
int main(){
 
    char org[] = "ABABABABABD";
    char str[] = "ABABD";
    int ans = KMP(org,str);
    cout << ans <<endl;
 
    return 0;
}

输出6，即经过6位，在第七位发生匹配