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

KMP字符串模式匹配算法简单匹配算法简单匹配算法简单匹配算法简单匹配算法intIndex_BF(charS,charT,intpos)/*若串S中从第pos(S的下标0posS0!=S1,S1!=S2,所以S1!=T0,S2!=T0.还是从理论上间接比较了。S假设S不变，在S中搜索T=“abaabd”。这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”。这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”。这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。三三.怎么求串的模式值怎么求串的模式值nextn定义定义：（1）next0=-1意义：任何串的第一个字符的模式值规定为-1。（2）nextj=-1意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但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）的其他情况。01）求T=“abcac”的模式函数的值。next0=-1根据（1）next1=0根据(4)因（3）有1=kj;不能说，j=1,Tj-1=T0next2=0根据(4)因（3）有1=kj;（T0=a）!=（T1=b）next3=-1根据(2)next4=1根据(3)T0=T3且T1=T4即下标01234Tabcacnext-100-1102）来个复杂点的，求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四四.串串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;