1. 原由

緊接上文，我們知道了暴力匹配的算法在時間運行上的缺陷，假設字符串T的長度為n，字符串P的長度為m，則整個算法的時間復雜度為O( n * m )，而對于一個復雜的現(xiàn)實情況而言 n >> m >> 2 （即n遠遠大于m，m遠遠大于常數(shù)），這樣的計算計算機的負擔很重。

請思考一個暴力匹配的情況：

給定一個主字符串

T = “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)

同時給定模式串 P = “AAAAAB”（6位）

試問搜索的情況，很顯然，暴力搜索對于每一次搜索，都要搜索到最后一個字符才能進行下一輪的搜索，因此進行的計算近似可以理解為：O(47 * 6) ，對于這樣很少的數(shù)據(jù)已經(jīng)有很高的計算量了。

KMP算法一種改進的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年聯(lián)合發(fā)表，KMP算法又稱克努特-莫里斯-普拉特操作， KMP算法與前文的暴力匹配算法，核心的區(qū)別就是沒有不匹配的回溯，而是根據(jù)整個字符串的情況進行一次位移，這樣大大減少了回溯產(chǎn)生的缺陷，KMP算法的時間復雜度可以優(yōu)化到 O( n + m)級別，是二次優(yōu)化到線性的程度。

2.構造next表(以-1開頭)

對于模式串P而言，我們需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后綴，并且求這個最大的完全相等的前后綴，如一個模式串”ABCABDE”對于第倒數(shù)第二位字符而言，其符合情況的前后綴就是”AB”，而最后一位則沒有完全相等的前后綴。

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

我們需要求的就是每一個字符其相對應的最大前后綴數(shù)，這樣與模式串P一一對應的表稱之為next表。

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

那么我們該如何實現(xiàn)代碼呢？

對于每一個當前需要判斷的字符而言，在構造next表時，應該向前進行比對，以上一個已經(jīng)判斷的情況為基礎（初始值賦-1，部分教程中初始值賦0，兩者沒有實質區(qū)別），后綴如果+1位置的字符與前綴+1位置的字符相等，則next[i]就是next[i-1]+1，而如果不相等，則說明無法匹配，則next[i]=0。

3. KMP實現(xiàn)

與暴力匹配極其相似，利用while循環(huán)的條件控制， 進行匹配失敗時，只需要將失敗的模式串P的索引指向next表中對應的數(shù)值即可，其余匹配照舊線性執(zhí)行即可。

4. 實現(xiàn)代碼（僅作參考）

#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，即經(jīng)過6位，在第七位發(fā)生匹配