搬运自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[48]中的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算法啦。
