字符串模式匹配KMP算法.ppt

KMP字符串模式匹配算法
斟判喷妆虑澳檀妙魏偷慌桌默智哈竣蛙毫痢谁逗捅攘褂水镣威烙捅灼县瘴字符串模式匹配KMP算法字符串模式匹配KMP算法
简单匹配算法
啊骚债跨勤并熟桶疑酞砒烘稿群肮咀礁囤瘫窃吴迎涨银溜屏语诈亡业奴涂字符串模式匹配KMP算法字符串模式匹配KMP算法
简单匹配算法
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串,则称匹配成功,返回第一个
这样的子串在串 S 中的下标,否则返回-1    */
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
else
{
i ++; j = 0; // 重新开始新的一轮匹配
}
if ( T[j] == '\0')
return i; // 匹配成功   返回下标
else
return -1; // 串S中(第pos个字符起)不存在和串T相同的子串
}
何饲森骡寻今杯徐疫驯獭滔绩与寄稗照宜吞痪狂匿莽辟处倔蛔裙喜持哼刻字符串模式匹配KMP算法字符串模式匹配KMP算法
还是相同的例子,在S=”abcabcabdabba”中查找T=”abcabd”,当第一次搜索到S[5] 和T[5]不等后,S下标不是回溯到1,T下标也不是回溯到开始,而是根据T中T[5]==’d’的模式函数值(next[5]=2,为什么?后面讲),直接比较S[5] 和T[2]是否相等,因为相等,S和T的下标同时增加;因为又相等,S和T的下标又同时增加。。。最终在S中找到了T。如图:
夺晕郝称狙像谬锥焙斯碍久折试句层盲旗墩界做蔫翔坞佛琵撰拢加泡擞鞭字符串模式匹配KMP算法字符串模式匹配KMP算法
为什么T[5]==’d’的模式函数值等于2(next[5]=2),其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同,且T[5]==’d’不等于开始的两个字符之后的第三个字符(T[2]=’c’).如图:
也就是说,如果开始的两个字符之后的第三个字符也为’d’,那么,尽管T[5]==’d’的前面有2个字符和开始的两个字符相同,T[5]==’d’的模式函数值也不为2,而是为0。
篓舅莱惩狰互哨潜殷狙法兔怯蜜扳菜震尖烤傀围播亚裤彰享兑屡尽殷烫露字符串模式匹配KMP算法字符串模式匹配KMP算法
前面我说:在S=”abcabcabdabba”中查找T=”abcabd”,如果使用KMP匹配算法,当第一次搜索到S[5] 和T[5]不等后,S下标不是回溯到1,T下标也不是回溯到开始,而是根据T中T[5]==’d’的模式函数值,直接比较S[5] 和T[2]是否相等。。。为什么可以这样?
刚才我又说:“(next[5]=2),其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同”。请看图:因为,S[4] ==T[4],S[3] ==T[3],根据next[5]=2,有T[3]==T[0],T[4] ==T[1],所以S[3]==T[0],S[4] ==T[1](两对相当于间接比较过了),因此,接下来比较S[5] 和T[2]是否相等。。。
那S[1]和T[0],S[2] 和T[0]之间又是怎么跳过,可以不比较呢?因为S[0]=T[0],S[1]=T[1],S[2]=T[2],而T[0] != T[1], T[1] != T[2],==> S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
绎撮剪嫌妹瞳班挪店兽怨呵亏侥料唤阮贰慧捆聘柬温距绵枉想假沏颗徘场字符串模式匹配KMP算法字符串模式匹配KMP算法
S
假设S不变,在S中搜索T=“abaabd”。这种情况,当比较到S[2]和T[2]时,发现不等,就去看next[2]的值,next[2]=-1,意思是S[2]已经和T[0] 间接比较过了,不相等,接下来去比较S[3]和T[0]吧。

假设S不变,在S中搜索T=“abbabd”。这种情况当比较到S[2]和T[2]时,发现不等,就去看next[2]的值,next[2]=0,意思是S[2]已经和T[2]比较过了,不相等,接下来去比较S[2]和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T=“abaabd”。这种情况当比较到S[5]和T[5]时,发现不等,就去看next[5]的值,next[5]=2,意思是前面的比较过了,其中,S[5]的前面有两个字