搬運(yùn)自CSDN博客：KMP算法中特征值數(shù)組next的計(jì)算與使用

在待匹配字符串P中，對(duì)于位置i衰倦，我們把P(0~i)中最大相同前綴子串和后綴子串的大小成為i的特征值，其組成的數(shù)組next[P.length]稱為特征值數(shù)組欺嗤。

那么如何求出next數(shù)組呢减余？

next[i-1]表示P(0~i-1) 中最大相同前綴子串和后綴子串的大小，假設(shè)next[i-1]=k府怯，就說明P(0~i-1)中前k個(gè)字符和后k個(gè)字符匹配刻诊，再比較P[i]時(shí)就應(yīng)該從位置k+1開始比，即比較P[i]與P[next[i-1]]

如果P[i]等于P[next[i-1]]牺丙，就表明P(0~i)中前k+1個(gè)字符和后k+1個(gè)字符匹配则涯，即next[i] = k+1 (也就是next[i-1])

如果P[i]不等于P[next[i-1]]，你就知道(i-next[i-1]~i)不能與(0~next[i-1])匹配
但你不知道(i-next[i-1]~i)的后綴子串能不能和(0~next[i-1])的前綴子串匹配
而你又知道(0~next[i-1]-1)能和(i-next[i-1]~i-1)匹配(內(nèi)容完全相同)。
那么你就可以把s[i]接到位置k上粟判，即直接考察子串(0~k-1)+s[i]亿昏，就能知道“(i-next[i-1]~i)的后綴子串”與“(0~next[i-1])的前綴子串”這兩個(gè)子串的匹配情況。

舉個(gè)例子：

代碼如下：

int * getNext(string s)  
{  
    unsigned int m =s.length();  
    int * Next = newint[m];  
    Next[0] = 0;  
    int k;  
    for(unsigned int i= 1 ; i < m ; i++)  
    {  
        k = Next[i -1];  
        while(k > 0&& s[k] != s[i])  
            k = Next[k- 1];  
        /** 
        **  s[k] != s[i] 
            從k再往后(k~i-1)比就沒有意義了 
            但你不知道在k之前(0~k-1)能不能匹配 
            考察范圍從i變成k易迹，相當(dāng)于把s[i]接到k上 
        ** 
        **/  
        if(s[k] ==s[i])  
            Next[i] =k + 1;  
        else  
            Next[i] =0;  
    }  
    return Next;  
}  

那么如何在KMP匹配過程中使用next數(shù)組呢宰衙？

代碼如下：

int getSubString(string target , string pattern , int startIndex = 0)  
{  
    int pl = pattern.length();  
    int tl = target.length();  
    if(tl - pl - startIndex < 0)  
        return -1;  
    int * next = new int[pl];  
    next = getNext(pattern);  
    int j = 0;  //pattern[j]  
    for(int i = startIndex ; i < tl ; i++)   //target[i]  
    {  
        while(j > 0 && pattern[j] != target[i])  
        {  
            j = next[j - 1];  
        }  
        if (pattern[j] == target[i])  
        {  
            j++;  
        }  
        if(j == pl)  
            return i-j+1;  
    }  
    return -1;  
  
}  

等等，j=next[j-1]什么鬼睹欲？

為了理解j=next[j-1]供炼，我們?cè)倥e個(gè)例子：

目標(biāo)字符串T:DBCABCEABC CABCABCDE
待匹配字串P:ABCEABCD
T[0],T[1],T[2]都不匹配，直接過窘疮。
從T[3]開始一直匹配到T[9]均與P匹配袋哼。
然而T[10]與P[7]不匹配(i=10,j=7)
這時(shí)我們應(yīng)該適當(dāng)調(diào)整i和j的位置。
一個(gè)比較容易想到的思路就是將T的位置跳到第二個(gè)ABC的A上闸衫，P跳到第一個(gè)字符A
對(duì)于i涛贯，先跳到匹配P之前的位置：i -= j，再跳到下一個(gè)ABC上蔚出，也就是i += j – next[j-1]弟翘。綜上，i = i – next[j-1]骄酗。
對(duì)于j稀余，直接跳到初始位置，j = 0趋翻。
然而如果i睛琳，j同時(shí)變化會(huì)影響代碼的簡(jiǎn)潔度，更重要的是嘿歌，如果i往回跳的話會(huì)影響算法的運(yùn)行效率掸掏。所以我們只要改變j相對(duì)于i的位置就可以了。
j相對(duì)于i來向后移了：j-next[j-1]宙帝。
所以丧凤，j-=(j-next[j-i])，即j=next[j-1]

通過對(duì)next數(shù)組的理解步脓，我們就可以愉快地使用KMP算法啦愿待。