5第五章串、数组和广义表.ppt

**************************************************************************************************看一个模式匹配的例子。设主串ob=“ZWWZWZ”,模式串pat=“ZWZ”,主串ob的长度为m=6,模式串pat的长度为n=3,用变量i指示主串ob的当前比较字符的下标,用变量j指示模式串pat的当前比较字符的下标。此例的模式匹配过程如图5-1所示。匹配过程又一示例例如主串ob=“ababcabcacbab”;模式串pat=“abcac”位序0123456789111012第一趟匹配ababcabcacbab(i=2)i从0开始abc(j=2)失败第二趟匹配ababcabcacbab(i=1)i从1开始a(j=0)失败第三趟匹配ababcabcacbab(i=6)i从2开始abcac(j=4)失败第四趟匹配ababcabcacbab(i=3)i从3开始a(j=0)失败第五趟匹配ababcabcacbab(i=4)i从4开始a(j=0)失败第六趟匹配ababcabcacbab(i=10)i从5开始abcac(j=5)成功!对于一般的模式匹配过程如图5-2所示,这里给出了某一趟比较的状态和下一趟比较时下标变化的一般过程。算法描述:intString::find(constStringpat)//从主串(即被调用串对象)的第0个位置的字符开始比较{inti=0,j=0;if(size==1||pat.size==1)return–1;//主串ob为空或模式串pat为空intString::find(constStringpat){//从主串(即被调用串对象)的第0个位置的字符开始比较inti=0,j=0;if(size==1||pat.size==1)return–1;//主串ob为空或模式串pat为空while(isize-1jpat.size-1){//逐趟比较if(p[i]==pat.p[j])//比较p[i]和pat.p[j],//这里p是串类String的私有数据成员{i++;j++;}else{i=i-j+1;//i回退j=0;}}//whileif(j==pat.size-1)returni-pat.size+1;//pat扫描完,匹配成功return–1;//在p中找不到pat}Brute-Force算法是一种带回溯的算法,也叫朴素的模式匹配算法。在最坏情况下,最多要比较m-n+1趟,每趟比较在最后才出现不等,要做n次比较,总比较次数要达到(m-n+1)?n。通常n会远远小于m,因此,算法的最坏情况下运行时间为O(m*n)。在最好情况下的时间复杂度为O(n),即主串的前n个字符刚好就等于模式串的n个字符。2.模式匹配的KMP算法KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt三人同时发现的。该算法是Brute-Force算法的改进。它消除了Brute-Force算法的如下缺点:主串ob下标i在若干次对应的字符比较相