现在的位置: 首页 > 综合 > 正文

2014年06月03日

2019年02月16日 ⁄ 综合 ⁄ 共 287字 ⁄ 字号 评论关闭
关于KMP算法的模式函数值的理解
next[0]=-1;next[j]=-1;a.当开头的1-k个字符与j前面的1-k个字符不相同;b.相同但是T[j]==T[k],相当于又得从头匹配;
假设s[i]!=t[j],那么如果t[j]==t[k],那么间接地,s[i]!=t[k],所以只能从头开始。
next[0]=k;当T[1.... k-1]==T[j-k+1,.......j-1],那么当失配的时候,T[j]前的一定是匹配的,所以用T[1.... k-1]来代替T[j-k+1,.......j-1],相当于间接匹配了,那么模式串向右移动的距离就是k。
除上;next[j]=0;

抱歉!评论已关闭.