字符串模式匹配KMP算法精品文稿.ppt

《字符串模式匹配KMP算法精品文稿.ppt》由会员分享，可在线阅读，更多相关《字符串模式匹配KMP算法精品文稿.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、字符串模式匹配KMP算法第1页，本讲稿共11页简单匹配算法简单匹配算法第2页，本讲稿共11页简单匹配算法简单匹配算法intIndex_BF(charS,charT,intpos)/*若串S中从第pos(S的下标0posS0!=S1,S1!=S2,所以S1!=T0,S2!=T0.还是从理论上间接比较了。第6页，本讲稿共11页S假设S不变，在S中搜索T=“abaabd”。这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”。这种情况当比较到S2和T2时，发现不

2、等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”。这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。第7页，本讲稿共11页三三.怎么求串的模式值怎么求串的模式值nextn定义定义：（1）next0=-1意义：任何串的第一个字符的模式值规定为-1。（2）nextj=-1意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k

3、个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad”则next6=-1，因T3=T6（3）nextj=k意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj!=Tk（1kj）。即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1且Tj!=Tk.（1kj）;（4）nextj=0意义：除（1）（2）（3）的其他情况。第8页，本讲稿共11页01）求T=“abcac”的模式函数的值。next0=-1根据（1）next1=0根据(4)因（3）有1=kj;不能说，j=1,Tj-1=T0next2=0根据(4)因（3）有1=kj;（T0=a）!

4、=（T1=b）next3=-1根据(2)next4=1根据(3)T0=T3且T1=T4即下标01234Tabcacnext-100-11第9页，本讲稿共11页02）来个复杂点的，求T=”ababcaabc”的模式函数的值。next0=-1根据（1）next1=0根据(4)next2=-1根据(2)next3=0根据(3)虽T0=T2但T1=T3被划入（4）next4=2根据(3)T0T1=T2T3且T2!=T4next5=-1根据(2)next6=1根据(3)T0=T5且T1!=T6next7=0根据(3)虽T0=T6但T1=T7被划入（4）next8=2根据(3)T0T1=T6T7且T2!=T8即下标012345678Tababcaabcnext-10-102-1102第10页，本讲稿共11页四四.串串T的模式值的模式值nextn的函数的函数voidget_nextval(constchar*T,intnext)/求模式串求模式串T的的next函数值并存入数组函数值并存入数组next。intj=0,k=-1;next0=-1;while(Tj!=0)if(k=-1|Tj=Tk)+j;+k;if(Tj!=Tk)nextj=k;elsenextj=nextk;elsek=nextk;第11页，本讲稿共11页