關于KMP算法中next數組和nextVal數組求法的整理

比較經典的例子：

位數	一	二	三	四	五	六	七	八
模式串	a	b	a	a	b	c	a	c
next	1	1	2	2	3	1	2
next val	1	2	1	3	2

next數組的求解方法是：

• 第一位的next值為0，第二位的next值為1，後面求解每一位的next值時，根據前一位進行比較。
• 首先将前一位與其next值對應的内容進行比較，
  • 如果相等，則該位的next值就是前一位的next值加上1；
  • 如果不等，
    • 向前繼續尋找next值對應的内容來與前一位進行比較，直到找到某個位上内容的next值對應的内容與前一位相等為止，則這個位對應的值加上1即為需求的next值；
    • 如果找到第一位都沒有找到與前一位相等的内容，那麼需求的位上的next值即為1。

具體計算next數組過程如下：

1. 前兩位必定為0和1。

2. 計算第三位的時候，看第二位b的next值，為1，則把b和1對應的a進行比較，不同，則第三位a的next的值為1，因為一直比到最前一位，都沒有發生比較相同的現象。

3. 計算第四位的時候，看第三位a的next值，為1，則把a和1對應的a進行比較，相同，則第四位a的next的值為第三位a的next值加上1。為2。因為是在第三位實作了其next值對應的值與第三位的值相同。

4. 計算第五位的時候，看第四位a的next值，為2，則把a和2對應的b進行比較，不同，則再将b對應的next值1對應的a與第四位的a進行比較，相同，則第五位的next值為第二位b的next值加上1，為2。因為是在第二位實作了其next值對應的值與第四位的值相同。

5. 計算第六位的時候，看第五位b的next值，為2，則把b和2對應的b進行比較，相同，則第六位c的next值為第五位b的next值加上1，為3，因為是在第五位實作了其next值對應的值與第五位相同。

6. 計算第七位的時候，看第六位c的next值，為3，則把c和3對應的a進行比較，不同，則再把第3位a的next值1對應的a與第六位c比較，仍然不同，則第七位的next值為1。

7. 計算第八位的時候，看第七位a的next值，為1，則把a和1對應的a進行比較，相同，則第八位c的next值為第七位a的next值加上1，為2，因為是在第七位和實作了其next值對應的值與第七位相同。

nextval數組的求解方法：

• 第一位值為1，nextval[1]=0。
• 從第二位開始，若要求第i位的nextval[i]，将next[i]的值對應的位的值與i的值進行比較（例如，當i=3時，next[3]=1對應的位數下的字元為‘a’，第i位的值為‘a’），
  • 若目前字元的值與目前字元下next值所對應位數的值不同，則目前字元的nextval值為目前字元對應的next值
  • 若目前字元的值與目前字元下next值所對應位數的值相同，則目前字元的nextval值為目前字元對應next值的nextval值

具體計算nextval的過程如下：

位數	一	二	三	四	五	六	七	八
模式串	a	b	a	a	b	c	a	c
next	1	1	2	2	3	1	2
next val	1	2	1	3	2

1. 第一位的nextval值必定為0，第二位如果與第一位相同則為0，如果不同則為1。

2. 第三位的next值為1，那麼将第三位和第一位進行比較，均為a，相同，則第三位的nextval值第一位的nextval值，為0。

3. 第四位的next值為2，那麼将第四位和第二位進行比較，不同，則第四位的nextval值為其next值，為2。

4. 第五位的next值為2，那麼将第五位和第二位進行比較，相同，則第五位的nextval值為第二位的nextval值，為1。

5. 第六位的next值為3，那麼将第六位和第三位進行比較，不同，則第六位的nextval值為其next值，為3。

6. 第七位的next值為1，那麼将第七位和第一位進行比較，相同，則第七位的nextval值為0。

7. 第八位的next值為2，那麼将第八位和第二位進行比較，不同，則第八位的nextval值為其next值，為2。

獲得nextval，代碼示例（《資料結構》嚴蔚敏）：

void get_nextval(SString T, int nextval []){
    i = 1;
    nextval[1] = 0;
    j = 0;
    while(i < T[0]){
        if (j == 0 || T[i] == T[j]){
            ++i;  ++j;
            if (T[i] != T[j]){
                nextval[i] = j
            } else{
                nextval[i] = nextval[j]
            }
        }else{
            j = nextval[j];
        }
    }
}
           

練練手：

可在“aaaab”内進行驗證：

模式串 a a a a b

next值 0 1 2 3 4

nextval值 0 0 0 0 4