KMP----next數組 最長相同前字尾 遞歸求法解釋

了解遞歸（推）求解next數組的代碼是個難點，對于剛入門來說

next數組求解的時候是 已知next[0....j]，next[j]=k.求解next[j+1]

首先next[j]=k的含義是說前j-1個字元最長相同前字尾是k，也說明字首的最後一個字元下标是k-1

如果p[j]==p[k],那很明顯是next[j+1]=k+1;

p[j]!=p[k]時，這時候

關鍵記住一句話：模式串的自我比對

想一想KMP是怎麼減少重複比較的，不就是移動的時候跳過一些元素嗎，根據什麼跳的，根據next數組跳的，為什麼？因為模式串和文本串在失配前的字元是相等的！如果已經比對相等的字元串裡面有相同前字尾，那我不就可以拿字首的最後一個字元的後一個字元 和失配字元 直接比較嗎？

比如ADAC和ABAD

在C、D比較時候，失配了，是不是把ABAD往前移動 j-next[j] 等價于

也就是把 p[next[j]]（在這裡是p[1]也就是D）和目前字元D比較

 那麼模式串 ADACADADFGH  在計算  ADACADAD  最長相同前字尾是多少

當發現C、D失配

此時就相當于 ADAC和ADAD作比對

也就是如下過程

C位置的next是1（ADA），也就是拿ADAC中的D來和 ADAD作比對

此時p[next[k]==p[j]    然後next=k+1=1+1=2

k=next[k]相當于KMP算法中的j-next[j]，一個是“顯式”移動，一個是直接改變p[k]中的下标，本質相同

代碼如下

void GetNext(char* p,int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = next[0];
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示字首，p[j]表示字尾
        if (k == -1 || p[j] == p[k]) 
        {
            //++k;
            //++j;
            //next[j] = k;
            next[j+1] = k+1;
            k++;j++;
        }
        else 
        {
            k = next[k];
        }
    }
}
           

說白了，你不和我相配，我再遞歸找你前面有沒有相同字首字尾，一直找到next[0]=-1為止，此時next[j]=k+1=-1+1=0