KMP算法

與BF算法相比，KMP的改進(jìn)之處在于圣蝎，當(dāng)主串當(dāng)前指針（下標(biāo)）字符與模式串當(dāng)前指針（下標(biāo)）字符不相等時(shí)刃宵，主串的指針i不需要回溯，而是利用已經(jīng)得到的"部分匹配"的結(jié)果徘公，將模式串盡量的右移牲证，繼續(xù)進(jìn)行匹配！

注：統(tǒng)一关面，本篇討論的字符串的下標(biāo)都是從0開始的

例如：

Next數(shù)組

注：如何理解 j = 0 時(shí)拴驮，next[0] = -1?

失配于模式串首字符流程

KMP算法Code框架 ： 按以上定義實(shí)現(xiàn)（Next[]構(gòu)建下面分析）

/*
@ Author : z
@ Date : 2018.7.30
@ Title : KMP
@ In : str      主串
       substr   模式串
@ Out : 
*/
#include <string>
int  KMP(string str, string substr)
{
    1. 創(chuàng)建模式串substr的next[ ] 數(shù)組
    int * next = BuildNext(substr);    

    int str_len = str.length();
    int substr_len = substr.length();
    int i = 0;      //主串下標(biāo)指針
    int j = 0;      //模式串下標(biāo)指針

    while (i < str_len && j < substr_len)
    {
        if ( (0 > j)  || ( str[i] == substr[j]) )
        {     通配符匹配或字符匹配
            i ++唆鸡；
            j ++;       // 攜手共進(jìn)
        }
        else
        {  失配，模式串盡量右移，即指針 j 左移 = next[j] 逗旁， i 不變
            j = next[j];
        }
    }// end_while

    delete []next;    //釋放next[]數(shù)組

    return i-j;     //  >= 0英古，匹配成功，且返回主串中模式串位置
                    //  < 0 , 匹配失敗
}

Key：關(guān)鍵在于模式串next[]數(shù)組的構(gòu)建，下面介紹！！藐石！

根據(jù)上面 Next數(shù)組 的定義實(shí)現(xiàn) next[ ]表的構(gòu)造

利用遞推來構(gòu)造 next[ ]表青自，以下：

已知 next[ j ] 的值雷滚，如何高效計(jì)算 next[ j + 1 ]

注 : 嚴(yán)格按定義商源，肯定能實(shí)現(xiàn)出爹，重點(diǎn)在于理解梢为！

next[ ]構(gòu)建Code

@ Author : zzz
@ Date   : 2018.7.30
@ Title  : Build next
@ In     : str   字符串
@ Out    : 

#include <string>

int * BuildNext(string str)
{
    int len = str.length();
    int j = 0;           // "主"串指針

    int * Next = new int[len];   // Next[] 表

/************************************************************/
    # 初始化 Next[0] = -1,
    # str[-1]作為通配符粟害，此處 t 可視為記錄：最大公共前后綴的長度
/************************************************************/
    int t = Next[0] = -1;

    while ( j < len-1)
    {
        if ((0 > t) || (str[j] == str[t]))
        {//哨兵匹配 即 t = -1 或 字符匹配
            Next[++j] = ++t;
        }
        else
        {//失配 , 遞推！！！
            t = Next[t] ;      
        }
    }

    return Next;
}

分析上面代碼中循環(huán)中的 if 和 else

• if ((0 > t) || (str[j] == str[t]))是分析中的情況1,next[j+1] = next[j] + 1，next[j]用 t 記錄

• else : t = Next[t]
  

舉個(gè)栗子恰聘，展示Next[]數(shù)組的構(gòu)建過程

依此類推

else的遞推過程

KMP - Next[ ] 數(shù)組的優(yōu)化

反例

改進(jìn) Next[ ] Code

@ Author : zzz
@ Date   : 2018.7.30
@ Title  : 改進(jìn)Next
@ In     : str字符串
@ Out    : 

#include <string>

int * BuildNext(string str)
{
    int len = str.length();
    int j = 0;           // "主"串指針

    int * Next = new int[len];   // Next[] 表

/************************************************************/
    # 初始化 Next[0] = -1,
    # str[-1]作為通配符排作，此處 t 可視為記錄：最大公共前后綴的長度
    # t 也可視為模式串指針，大小為最大公共前后綴的長度
/************************************************************/
    int t = Next[0] = -1;

    while ( j < len-1)
    {
        if ((0 > t) || (str[j] == str[t]))
        {// 匹配 ， 改進(jìn)處！！！
            j ++;
            t ++;
            Next[j] = ( str[j] != str[t] ? t : Next[t] );            // !!! !!!
        }
        else
        {//失配 
            t = Next[t] ;      
        }
    }

    return Next;
}

改進(jìn)Next數(shù)組構(gòu)建，遞推的過程！