《表1 BF算法：浅析KMP算法中next数组值计算》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《浅析KMP算法中next数组值计算》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

传统的next数组使用递推的思想，对于模式串T，且已知next[j]=k即T0Tk-1”=“Tj-kTj-1”时，next[j+1]=next[j]+1=k+1，但T0Tk-1Tk”≠“Tj-kTj-1Tj”。换言之，当Tk!=Tj时，有长度为k+1的相同前缀后缀，不能再简单的令:next[j+1]=next[j]+1，这时若能在前缀“T0Tk-1Tk”中不断的递归k=next[k]，找到一个字符Tk’使得Tk’=Tj，且满足T0Tk'-1Tk'=Tj-k'Tj-1Tj，从而next[j+1]=k’+1=next[k']+1，否则next[j+1]=0。运用这个思想对字符串“edeedee”求出的next数组值为0，1，1，2，2，3，4从描述过程不难看出其抽象难懂，极易造成错误的结果。