《表1 比较次数：关于kmp算法改进的探讨》

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

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

《关于kmp算法改进的探讨》

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

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

取主串s为qvqbqvcbdw，模式串t为qvcbd时，当初始值都为1时s[1]=t[1]，i和j的值各加1，i=2，j=2，根据改进算法的程序，这样循环比较直至s[3]≠t[3]时，重新置j=1，k=i-j+2=2，i加1后i=4，这时k的值小于i且j的值小于t串的长度，将t[1]的值与s[k]即s[2]的值进行比较后t[1]≠s[2]，k值加1后k=2+1=3，j重新置1即j=1，这时k的值小于i且j的值小于t串的长度，将s[k]即s[3]与t[1]比较后s[3]=t[1]，k的值加1即k=3+1=4，j的值加1后j=2，这时k的值不小于i，条件不满足，回到程序起始状态，将t串第二个字符与s串的第四个字符比较，s[i]即s[4]的值与t[2]的值进行比较，但s[4]≠t[2]，k的值为k=4-2+2=4，j重新置1即j=1，i的值加1后i=5，这时k的值小于i，将s[k]即s[4]与t[1]进行比较，s[4]≠t[1]，k值加1后k=4+1=5，j重新置1即j=1，这时k的值不小于i，条件不满足，回到程序起始状态比较s[5]与t[1]的值后s[5]=t[1]，i和j的值各加1，i=5，j=2，接着比较s[6]和t[2]的值依然相等，以此类推，直至比较到s[8]=t[5]后，j的值大于t串的长度，找到模式串在主串的起始位置为5，其比较次数如表1所示: