KMP算法中特征值数组next的计算与使用

搬运自CSDN博客：KMP算法中特征值数组next的计算与使用

在待匹配字符串P中，对于位置i，我们把P(0~i)中最大相同前缀子串和后缀子串的大小成为i的特征值，其组成的数组next[P.length]称为特征值数组。

那么如何求出next数组呢？

next[i-1]表示P(0~i-1) 中最大相同前缀子串和后缀子串的大小，假设next[i-1]=k，就说明P(0~i-1)中前k个字符和后k个字符匹配，再比较P[i]时就应该从位置k+1开始比，即比较P[i]与P[next[i-1]]

如果P[i]等于P[next[i-1]]，就表明P(0~i)中前k+1个字符和后k+1个字符匹配，即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)匹配(内容完全相同)。
那么你就可以把s[i]接到位置k上，即直接考察子串(0~k-1)+s[i]，就能知道“(i-next[i-1]~i)的后缀子串”与“(0~next[i-1])的前缀子串”这两个子串的匹配情况。

举个例子：

next[7]=4，表明P[0~3]与P[4~7]匹配
而P[8]不等于P[4]，则
”abbaa”!=”abbab”
但这两个子串的前四个字符是一样的，也就是P[4_8]中的P[47]等于P[0~4]中的P[0~3]
但是你不能断定P[4~8]的后缀子串能否与P[0~4]的前缀字串是否匹配，而你又知道P[0~3]==P[4~7]，所以你可以把P[8]接到P[0~3]后面来判定。

代码如下：

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，相当于把s[i]接到k上 
        ** 
        **/  
        if(s[k] ==s[i])  
            Next[i] =k + 1;  
        else  
            Next[i] =0;  
    }  
    return Next;  
}  

那么如何在KMP匹配过程中使用next数组呢？

代码如下：

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]，我们再举个例子：

目标字符串T:DBCABCEABC CABCABCDE
待匹配字串P:ABCEABCD
T[0],T[1],T[2]都不匹配，直接过。
从T[3]开始一直匹配到T[9]均与P匹配。
然而T[10]与P[7]不匹配(i=10,j=7)
这时我们应该适当调整i和j的位置。
一个比较容易想到的思路就是将T的位置跳到第二个ABC的A上，P跳到第一个字符A
对于i，先跳到匹配P之前的位置：i -= j，再跳到下一个ABC上，也就是i += j – next[j-1]。综上，i = i – next[j-1]。
对于j，直接跳到初始位置，j = 0。
然而如果i，j同时变化会影响代码的简洁度，更重要的是，如果i往回跳的话会影响算法的运行效率。所以我们只要改变j相对于i的位置就可以了。
j相对于i来向后移了：j-next[j-1]。
所以，j-=(j-next[j-i])，即j=next[j-1]

通过对next数组的理解，我们就可以愉快地使用KMP算法啦。