KMP算法中，当主串字符s[i]不等于子串字符t[j]时，希望知道s[i]接下来与子串哪个字符比较
目录
1 假设
- 主串S：‘s[1]s[2]…s[n]’
- 子串T：‘t[1]t[2]…t[m]’
- 一般地，n>=m
2 推导
-
已有部分匹配结果：
's[i-j+1]s[i-j+2]...s[i-1]' = 't[1]t[2]...t[j-1]' -
则必有
's[i-k+1]s[i-k+2]...s[i-1]'='t[j-k+1]t[j-k+2]...t[j-1]' -
当s[i]不等于t[j]时，子串T需要向右移动，假设此时s[i]应该与t[k]继续比较，k<j
-
则有新的部分匹配结果：
's[i-k+1]s[i-k+2]...s[i-1]'='t[1]t[2]...t[k-1]'且不存在k’<k满足
's[i-k'+1]s[i-k'+2]...s[i-1]'='t[1]t[2]...t[k'-1]' -
综合上述等式有：
't[1]t[2]...t[k-1]' = 't[j-k+1]t[j-k+2]...t[j-1]' -
若next[j]=k表示：当子串第j个字符与主串第i个字符不相等时，应该用子串第k个字符接着与主串第i个字符比较
- 需要向右移动
j-k个字符距离
- 需要向右移动
-
则有next数组的定义
3 next数组的定义
next[j] =
- 0 当j=1时
- max{k | 1<k<j，且't[1]t[2]...t[k-1]'='t[j-k+1]t[j-k+2]...t[j-1]'} 当此集合不空时
- 1 当其他情况时
即
4 解释
- 1<=k<j
- 1<=j<=m
- j=1时，不存在k，使得k<j，因此，next[j]=0，表示没有字符
- j>1时，
- 若j=2，显然有k=1
- 若j>2，则考虑部分匹配结果，取满足定义中等式的最大的k，可能的k值：j-1、j-2、…、1、0
- 又k=0，表示找不到满足定义中等式的k，因此，next[j]=1，归入其他情况
- 又k=1，表示子串第1个字符与主串第i个字符比较，意义特殊，单独列出，归入其他情况
- 区分：作为字符位置的k、表示不存在的k(即k=0)
5 代码实现
说明：
- 由next数组的定义，用递推的方法有：
- 显然，next[1]=0
- 设next[j]=k，则有：‘t[1]t[2]…t[k-1]’=‘t[j-k+1]t[j-k+2]…t[j-1]’
- 对next[j+1]，子串T对子串T进行模式匹配，
- 若t[k]==t[j]，则有：‘t[1]t[2]…t[k]’=‘t[j-k+1]t[j-k+2]…t[j]’，于是next[j+1]=k+1
- 若t[k]不等于t[j]，则考虑next[k]=k’，显然，1<k’<k<j
- 若t[k’]==t[j]，则next[j+1]=k’+1
- 若t[k’]不等于t[j]，则…，以此类推
- 直到不存在k’来参与比较时，认为k’=0，从而有next[j+1]=0+1=1，表示子串第1个字符与主串第i个字符比较
代码：
//函数名：get_next
//功能：求next数组的值
Status get_next(SString T, int next[])
{
int j = 1;
int k = 0;
//初值
next[1] = 0;
//j的范围：1<=j<=T[0]
while (j < T[0])
{
//若k=0，表示找不到k，next[j+1]=1，因此，j和k都需要往下移一位
//若T[j]==T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位
if (k==0 || T[j]==T[k])
{
++j;
++k;
next[j] = k;
}
else
{
//若T[j]不等于T[k]，则考虑next[k]=k'
k = next[k];
}
}
return OK;
}
6 例子
- 理论结果：
- 运行结果：
7 补充
-
next数组仍可以改进：
- 当子串T中出现【连续多个相同字符】时，若s[i]与t[j]不相等，而next[j]=k，t[j]==s[k]，从而s[i]与t[k]没有必要再比较
- 则有nextval数组
-
nextval数组
说明：
- 由next数组的定义，用递推的方法有：
- 显然，next[1]=0
- 设next[j]=k，则有：‘t[1]t[2]…t[k-1]’=‘t[j-k+1]t[j-k+2]…t[j-1]’
- 对next[j+1]，子串T对子串T进行模式匹配，
- 若t[k]==t[j]，则有：‘t[1]t[2]…t[k]’=‘t[j-k+1]t[j-k+2]…t[j]’，于是next[j+1]=k+1
- 若t[k]不等于t[j]，则考虑next[k]=k’，显然，1<k’<k<j
- 若t[k’]==t[j]，则next[j+1]=k’+1
- 若t[k’]不等于t[j]，则…，以此类推
- 直到不存在k’来参与比较时，认为k’=0，从而有next[j+1]=0+1=1，表示子串第1个字符与主串第i个字符比较
- 当t[k]==t[j]时，nextval[j+1]=k+1
- 对子串T，若t[j+1]
==t[ nextval[j+1] ]
==t[ nextval[ nextval[j+1] ] ]
==…，以此类推- 找到最小的k’，使得t[j+1]不等于t[k’]，从而nextval[j+1]=nextval[ nextval[j+1] ]=…=k’
- 若找不到这样的k’，则令k’=0，从而nextval[j+1]=nextval[ nextval[j+1] ]=…=0，表示找不到
//函数名：get_nextval
//功能：求nextval数组的值
Status get_nextval(SString T, int nextval[])
{
int j = 1;
int k = 0;
//初值
nextval[1] = 0;
//j的范围：1<=j<=T[0]
while (j < T[0])
{
//若k=0，表示找不到k，next[j+1]=1，因此，j和k都需要往下移一位
//若T[j]==T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位
if (k==0 || T[j]==T[k])
{
++j;
++k;
if (T[j] != T[k])
nextval[j] = k;
else
//因为从nextval[1]开始就一直取最小的k，
// 所以这里去找上一个k，即nextval[k]，就是要找的k'
nextval[j] = nextval[k];
}
else
{
//若T[j]不等于T[k]，则考虑next[k]=k'
k = nextval[k];
}
}
return OK;
}
运行结果：
- 如果考试的时候，让求字符串“abcaabbabcabaacbacba”的next数组值和nextval数组值，怎么快速求出来？【结果如下】
8 参考文献
- 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社, 2007.
补充：
水平不高，可能还有做得不够好的地方，
希望能和大家交流学习，
转载请注明出处。