下一个问题是如何求模式串的 next 函数值？
求 next 函数的过程是一个递推的过程：
1.首先由定义得 next[0]=-1，next[1]=0;
2.假设已知 next[j]=k，又 T[j] = T[k]，则显然有 next[j+1]=k+1；
3.如果 T[j]
T[k]，则令
k=next[k]，直至 T[j] 等于 T[k] 为止。由此可得下列求 next 函数值的算法，它和上述的KMP算法非常相似。
void get_next(char T[], int next[])
{
// 求模式串T的next函数值并存入数组 next。
j = 0; next[0] = -1; k = -1;
while ( T[j+1] != '\0' ) {
if (k = = -1 || T[j] = = T[k])
{ ++j; ++k; next[j] = k; }
else k = next[k];
}
} // get_next
1.虽然next定义中没有明确指出next[1]=0，但由0<k<j的条件很容易判断出next[1]只能等于0；
2.next[j]=k表明在T串中的字符T[k]之前存在一个长度最大的子串 "
...
"
和T串中的子串 "
...
"
相等，而现在又知道了
=
，这就是说，在字符T[k+1]之前存在着一个长度最大的子串使得等式
"
..."="
..."
成立，则根据next函数值的定义不就得到next[j+1]=k+1了吗？3.由于
，则等式
"
..."="
..."
不成立，也就是说，在字符T[k+1]之前不存在一个子串 "
..."
和子串 "
..."
相等，那么是否可能存在另一个值p<k，使等式 "
...
"="
..."
成立，这个 p 显然应该是 next[k]，因为这相当于一个"利用 next 函数值进行T串和T串的匹配"问题。 但是还有一种特殊情况需要考虑：
例如：
S = 'aaabaaabaaabaaabaaab'
T = 'aaaab'
此时因为T串的next函数值依次为-1,0,1,2,3,虽然匹配过程中指针 i 没有回溯，但对 i=3、7、11和15重复进行了多次的'b'是否等于'a'的操作。换句话说，如果
next[j]=k，那么此时应该看一下T[j]是否等于 T[k]，如果不等，则 next[j]=k，否则next[j]就应该取值 next[k]。例如上述T串的
next 函数值依次为-1,-1,-1,-1,3。由此改写求模式串的 next 函数值的算法如下。
算法 4.9void get_nextval(char T[], int next[])
{
// 求模式串T的next函数值并存入数组 next。
j = 0; next[0] = -1; k = -1;
while ( T[j+1] != '\0' ) {
if (k = = -1 || T[j] = = T[k]) {
++j; ++k;
if (T[j]!=T[k]) next[j] = k;
else next[j] = next[k];
} // if
else k = next[k];
} // while
} // get_nextval
