KMP算法的探索

KMP是字符串比對(duì)中一種高效的算法，在數(shù)據(jù)結(jié)構(gòu)課堂上時(shí)間短很難完全理解。
于是課后我又自己摸索了一番，根據(jù)自己的理解獨(dú)立編寫(xiě)了程序

規(guī)定

為了下文敘述方便先規(guī)定幾個(gè)統(tǒng)一的說(shuō)法：

• 文本串：被比對(duì)的字符串；
• 模式串：比對(duì)的模板字符串；
• 指針i：指向文本串正在比對(duì)位置的指針；
• 一系列指針：下文結(jié)合程序注釋；
• next數(shù)組、兩種字符串下標(biāo)均從1開(kāi)始；

BF-算法

字符串比對(duì)中的暴力算法，沒(méi)啥好說(shuō)的，文本串逐位與模式串進(jìn)行比較，不匹配則指針i回溯。例如：從i=1開(kāi)始匹配，匹配到i=5時(shí)失敗，回溯至i=2重新匹配。

next數(shù)組

關(guān)于KMP算法中最核心的思想蘊(yùn)含在next[]數(shù)組中，next數(shù)組下標(biāo)對(duì)應(yīng)著字符串下標(biāo)（下標(biāo)從1開(kāi)始，0位空置，至少我是空置）。顧名思義，next數(shù)組的值意義為本次“失配”后，下次匹配開(kāi)始的位置（模式串的下標(biāo)）。

思想動(dòng)畫(huà)

圖A:源自于B站視頻

圖B:源自于B站視頻

從圖A到圖B：第六位A失配后，很明顯模式串發(fā)生了向右的滑動(dòng)。
滑動(dòng)的依據(jù)：滑動(dòng)前箭頭左側(cè)的模式串前綴“AB”與后綴“AB”完全一致，由于箭頭左側(cè)已經(jīng)匹配成功，所以對(duì)應(yīng)的文本串也是一樣的。這時(shí)候向右滑動(dòng)既保證與文本串匹配，又避免了（滑動(dòng)后）箭頭左側(cè)重復(fù)匹配操作。
滑動(dòng)位數(shù)：即next數(shù)組的值。圖中若以next數(shù)組表示，即位next[3] = 3。

• 兩個(gè)‘3’均指模式串的第三位。翻譯過(guò)來(lái)就是：當(dāng)模式串中的第三位失配時(shí)，下一步從模式串的第三位繼續(xù)匹配。
• 進(jìn)一步抽象：有數(shù)組 next[x] = y，意思是：當(dāng)模式串中的第x位失配時(shí)，下一步從模式串的第y位繼續(xù)匹配。

上述 next[x] = y ，x沒(méi)什么好說(shuō)的就是模式串下標(biāo)，下一步匹配位置y是如何得到的呢？
根據(jù)上圖可以稍微總結(jié)一下：失配位置（箭頭）左側(cè)模式串前后綴一致的長(zhǎng)度L加1，就是y。這個(gè)也很好理解，相當(dāng)于我長(zhǎng)度為L(zhǎng)的子串已經(jīng)匹配好了，那么只需要從L+1處繼續(xù)匹配就好啦。

圖片源于B站

這張圖意在說(shuō)明，在我們找一致的前后綴（很多人稱為公共前后綴）的時(shí)候，是可能發(fā)生重疊的。

如果以上內(nèi)容你看懂了

你就理解了next數(shù)組的求法了：即找出失配位置前，模式串子串的公共前后綴的最大長(zhǎng)度L，并從L+1位開(kāi)始繼續(xù)匹配。

void cal_nextValue()
    {
        string t = compstr;
        int m = 0; //記錄能夠匹配的公共前后綴的最大長(zhǎng)度
        if (t.size() <= 0) return;
        next[1] = 0; //模式串第一位直接置0，該位置左側(cè)子串長(zhǎng)度為0
        if (t.size() <= 1) return;
        next[2] = 1;//第二位失配了，左側(cè)最大公共前后綴只能為1
         //從第三位開(kāi)始，在失配位置左側(cè)字符串尋找最長(zhǎng)子串為公共前后綴
        for (int i = 3; i < t.size(); i++)
        {
           // j為“左擋板”往右移動(dòng)限定后綴,k為“右擋板”往左移動(dòng)限定前綴
            for (int k = i - 2, j = 2; j < i; j++, k--)
            {
                int flag = 1;
                int j_ = j; //不改變擋板位置
              //后綴與前綴進(jìn)行比較
                for (m = 1; m <= k && j_ < i; m++, j_++)
                {
                  //字符不同則跳出循環(huán)，移動(dòng)擋板位置（縮小前后綴長(zhǎng)度）重新比較
                    if (t[j_] != t[m])
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag) break;
            }                 
             //循環(huán)結(jié)束時(shí)，由于for循環(huán)種“m++”實(shí)際匹配的最長(zhǎng)公共前后綴為m-1；
            next[i] = m; //從最長(zhǎng)公共前后綴下一位繼續(xù)匹配，即 m-1+1=m
        }

看下來(lái)我們會(huì)發(fā)現(xiàn)next數(shù)組的求解與文本串沒(méi)有關(guān)系，任何模式串都可以求出自己的next數(shù)組

比較字符串

• 其實(shí)next數(shù)組求解完了，比較字符串就很簡(jiǎn)單了。

• 先定義i和j兩個(gè)指針：i指向文本串；j指向模式串。

• 第一次仍是逐一比較，相同則i、j均右移一位。當(dāng)出現(xiàn)失配時(shí)，i不右移也不回溯，j根據(jù)next[j]的值移動(dòng)，讓移動(dòng)后的模式串繼續(xù)與第i位匹配比較。
  （當(dāng)指針j回退至0時(shí)，指針i、j需同時(shí)++。即若主串的第i個(gè)字符和模式的第1個(gè)字符不等，應(yīng)從主串的第i+1個(gè)字符重新匹配）
  循環(huán)結(jié)束后根據(jù)i、j指針位置即可判斷

void cal_KMP()
    {
        cal_nextValue();
        if (tempstr.size() < compstr.size())
            return;

        int i = 1;
        int j = 1;
        while (i < tempstr.size() && j < compstr.size())
        {

            if ((tempstr[i] != compstr[j]) && next[j] != 0)
                j = next[j];
            else
            {
                i++;
                j++;
            }
        }
        if (j == compstr.size()) //匹配成功
        {
            result.didhave = true;
            result.pos = i + 1 - (compstr.size()-1);
        }
        else if (i == tempstr.size() && j != compstr.size()) //匹配失敗
        {
            result.didhave = false;
            result.pos = -1;
        }
    }

教材簡(jiǎn)潔版

當(dāng)我自己摸索完去看了眼教材，發(fā)現(xiàn)上面求next數(shù)組的程序好短

void get_next(SString T, int next[]){
  //T位模式串
  i = 1;
  next[1] = 0;
  j = 0;
  while(i < T[0]){
    if(j == 0 || T[i] == T[j]){
      ++i;
      ++j;
      next[i] = j;  
    }  
    else  j = next[j];
  }
}

T[0]應(yīng)該是存放字符串長(zhǎng)度的
有一說(shuō)一我腦子不好挺難看懂。。放著有大佬會(huì)的也可以說(shuō)說(shuō)