计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn
这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：
又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标4。如图：
上述通过4次匹配，终于在S串中?查找?到T串，位置时4。
老师再次提出问题：在第一趟比较后，进行的第二趟、第三趟比较有必要吗？ 提问的形式：让学生讨论如下问题， 第一趟后，当S[6]≠T[6]时，
第二趟进行S[2]与T[1]比较是必要的吗？ 第三趟进行S[3]与T[1]比较是必要的吗？ 第四趟进行S[4]与T[1]比较是必要的吗？ 第四趟进行S[4]与T[2]比较是必要的吗？
如果是不必要的，那么第一趟后，当S[6]≠T[6]时， S[6]与T[ ？]比较是必要的呢！
解决问题：引入?KMP匹配算法?
4、KMP 匹配算法
KMP算法：KMP算法是对传统模式匹配算法的较大改进，在传统的模式匹配算法中，当出现主串中的字符与子串中的字符不等时，同时向前回溯了两个指针，一个是主串的指针，一个是子串的指针。而KMP算法的基本思路是在不回溯主串的指针，而只回溯子串的指针的情况下完成模式匹配，这样就省去了回溯主串指针进行比较的一部分时间。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。
计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn
还是相同的例子，在S=?abcabcabdabba?中查找T=?abcabd?，如果使用KMP匹配算法，当第一次搜索到S[6] 和T[6]不等后，S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T[6]==’d’的模式函数值（next[6]=3，为什么？后面讲），直接比较S[6] 和T[3]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。。。最终在S中找到了T。如图：
next[6]=3含义： 其实这个3表示T[6]==’d’的前面有2个字符和开始的两个字符相同?。请看图 ：因为，S[5] ==T[5]，S[4] ==T[4]，根据next[6]=3，有T[4]==T[1]，T[5] ==T[2]，所以S[4]==T[1]，S[5] ==T[2]（两对相当于间接比较过了），因此，接下来比较S[6] 和T[3]是否相等。
有人可能会问：S[4]和T[1]，S[5] 和T[2]是根据next[6]=3间接比较相等，那S[2]和T[1]，S[3] 和T[1]之间又是怎么跳过，可以不比较呢？因为S[1]=T[1]，S[2]=T[2]，S[3]=T[3]，而T[1] != T[2], T[2] != T[3],==> S[1] != S[2],S[2] != S[3],所以S[2] != T[1],S[3] != T[1]. 还是从理论上间接比较了。
5 . 怎么求串的模式值 next[n]
定义 ：
0 如果j=1
next[j]={ Max{k|1 （1）next[1]=0 意义：任何串的第一个字符的模式值规定为0。 （2）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k－1个字符与开头 的k－1个字符相等， 即: T[1]T[2]……T[k-1] == T[j-k+1]T[j-k+2]…T[j-1] （3）next[j]=1 其他情况。 计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn 例1）求T=?abcac?的模式函数的值。 下标 T next 例2） 求T=?ababcaabc? 的模式函数的值。 下标 T next 例3) 求 T=?abCabCad? 的模式函数的值。 下标 T next 课后题：求 T=? ababcabababc? 的模式函数的值。 6. next[n] 不足与改进： KMP的改进算法：KMP的改进算法主要是针对求NEXT数组的算法思想进行的改进。为了提高NEXT数组的效率，引入了NEXTVAL数组(即NEXT的改进值)。NEXTVAL避免了当出现匹配不成功时再接着进行重复比较的情况。比如：?abcdabce?模式串中，NEXT值为(0 1 1 1 1 2 3 4)，NEXTVAL值为(0 1 1 1 0 1 1 4)。当比较到T[7]=C不成功时，原NEXT的值跟T[3]比较，可事实上，T[3]也是C，与T[7]相同，所以可以直接跟T[1]比较。 举例 ：若T=?abcab?的模式函数的值 下标 T next 若S＝?abcadcabcab?， a 0 b 1 c 1 a 1 b 2 1 2 3 4 5 a 0 b 1 C 1 a 1 b 2 C 3 a 4 d 5 1 2 3 4 5 6 7 8 a 0 b 1 a 1 b 2 c 3 a 1 a 2 b 2 c 3 1 2 3 4 5 6 7 8 9 a 0 b 1 c 1 a 1 c 2 1 2 3 4 5 计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn next[n] 改进为nextval[n]： 如果T[j]!=T[k]，k=next[j] 否则k=next[k] 下标 T next 1 a 0 2 b 1 3 c 1 4 a 0 5 b 1
相关推荐：
loading