数据结构与算法设计PPT (12).pdf
第3章字符串3.2 字符串的模式匹配串的模式匹配 定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。示例 目标 T:“Beijing”模式 P:“jin”匹配结果=3第1趟Ta b b a b aPa b a第2趟Ta b b a b aPa b a第3趟Ta b b a b aPa b a第4趟Ta b b a b aP a b a穷举模式串的模式匹配int String:Find(String&pat)const/穷举的模式匹配char*p=pat.ch,*s=ch;int i=0;if(*p&*s)/当两串未检测完while(i=curLen-pat.curLen)if(*p+=*s+)/比较串字符if(!*p)returni;/相等else i+;s=ch+i;p=pat.ch;/对应字符不相等，对齐目标的/下一位置，继续比较return-1;穷举模式算法目标Tt0t1t2 tm-1 tn-1!模式patp0p1p2 pm-1目标Tt0t1t2 tm-1tm tn-1!模式patp0p1 pm-2 pm-1目标Tt0t1 titi+1 ti+m-2ti+m-1 tn-1 模式patp0p1 pm-2 pm-1穷举模式匹配效率分析每个位置进行全匹配比较利用已有的比较成果和模式的特征，跳过中间没必要比较的过程，提高效率a b a b c a b c a c b a b a b c a c 发现失败时a b c a c没必要：abcbcaa b c a c 没必要：abcaa b c a c 没必要：此位置和a比较过是相等的a b c a c 可以直接从模式串的第二个字符和当前位置的主串中的值比较克努特莫里斯普塔特操作（KMT算法）ab c a c:模式串的第一个字符a 比较时不相等发现失败时：只能从主串的下一个位置开始，和模式串中的第一个字符比较a b c a c:模式串的第二个字符b 比较时不相等发现失败时：从主串的当前位置开始，和模式串中的第一个字符比较a b c a c：模式串的第五个字符C比较时不相等发现失败时：从当前位置开始，和模式串中的第二个字符比较a b c a b c c：模式串的第7个字符比较不相等 时：从当前位置开始，和模式串中的第几个字符比较？KMT算法j 0 1 2 3 4 5 6 7 8 9 模式串a b a a b c a c滑动位数 一个整数，其含义代表下一步怎样去比较主串位置：子串和主串比较的当前字符位置0：子串从主串当前位置从下标0处比较第一对不同时，主串从下一个位置开始1：子串从主串当前位置对从模式串下标1处进行比较2：子串从主串当前位置对从模式串下标2处进行比较KMT算法j 0 1 2 3 4 5 6 7 8 9 模式串 a b a a b c a cfj 1 模式串 a b a a b c a c取子串的长度为1、2、3、4(k=0,1,2,3)长度为1的子串：a！b长度为2的子串：a b a b（p0 p1=p3 p4即 k=1 p0 pk=pj-k pj）长度为3的子串：a b a！a a b长度为4的子串：a b a a !=b a a bKMT算法穷举的模式匹配算法时间代价：最坏情况比较n-m+1趟，每趟比较m次，总比较次数达(n-m+1)*m 原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。改进的模式匹配(KMP)算法的时间代价：w 若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=nw 若每趟第m个不匹配，总比较次数最坏亦达到nKMT算法与穷举匹配性能对比Tt0t1 ts-1tsts+1ts+2 ts+j-1ts+jts+j+1 tn-1 Pp0p1p2 pj-1pjpj+1则有tsts+1ts+2 ts+j=p0p1p2 pj(1)为使模式P 与目标T 匹配，必须满足p0p1p2 pj-1 pm-1 =ts+1ts+2ts+3 ts+j ts+m如果p0p1pj-1 p1p2 pj(2)则立刻可以断定p0p1pj-1 ts+1ts+2 ts+j下一趟必不匹配KMT算法正确性证明同样，若p0p1pj-2 p2p3 pj则再下一趟也不匹配，因为有p0p1pj-2 ts+2ts+3 ts+j直到对于某一个“k”值，使得p0p1pk+1 pj-k-1pj-kpj且p0p1pk=pj-kpj-k+1 pj则p0p1pk=ts+j-kts+j-k+1 ts+j pj-kpj-k+1 pjKMT算法正确性证明k 的确定方法当比较到模式第j 个字符失配时，k 的值与模式的前j 个字符有关，与目标无关。利用失效函数f(j)可描述。利用失效函数f(j)的匹配处理如果j=0，则目标指针加 1，模式指针回到p0。如果j 0，则目标指针不变，模式指针回到pf(j-1)+1。失效函数的计算若设 模式P=p0 p1pm-2 pm-1=+-1,-.,0,=)(110)其它情况的最大整数且使得当jkjkjkppppppjkkjf!j 0 1 2 3 4 5 6 7 P P a b a a b c a c f f (j j )-1 1 -1 1 0 0 0 0 1 1 -1 1 0 0 -1 1示例：确定失效函数f(j)失效函数的计算第第1 1趟趟 目标目标a a c c a b a a b a a b c a c a a b ca b a a b a a b c a c a a b c模式模式a a b b a a b c a ca a b c a c j j=1=1 j j=f f(j j-1)+1=01)+1=0第第2 2趟趟 目标目标a a c c a b a a b a a b c a c a a b ca b a a b a a b c a c a a b c模式模式a a b a a b c a cb a a b c a c j j=0 =0 目标指针加目标指针加 1 1 第第3 3趟趟 目标目标a c a c a b a a ba b a a b a a a b c a c a a b ca b c a c a a b c模式模式a b a a ba b a a b c c a ca c j j=5=5j j=f f(j j-1)+1=21)+1=2第第4 4趟趟 目标目标a c a b a a b a c a b a a b a a a b c a ca b c a c a a b ca a b c模式模式(a ba b)a a a b c a ca b c a c 利用失效函数的匹配过程int String:fastFind(String pat)const/带失效函数的KMP匹配算法int posP=0,posT=0;int lengthP=pat.curLen,lengthT=curLen;while(posP lengthP&posT lengthT)if(pat.chposP=chposT)posP+;posT+;/相等继续比较else if(posP=0)posT+;/不相等else posP=pat.fposP-1+1;if(posP lengthP)return-1;else return posT-lengthP;利用失效函数的匹配的算法计算失效函数f j 的方法首先确定f 0=-1，再利用f j求f j+1。其中,f(1)j =f j,f(m)j=ff(m-1)j=-=+=+,01111)(jkppjfjfj(k)jfm 否则或的最小正整数可找到令 失效函数的计算方法voidString:fail()/计算失效函数intlengthP=curLen;f 0=-1;/直接赋值for(intj=1;j=0)i=f i;/递推if(*(ch+j)=*(ch+i+1)f j=i+1;elsef j=-1;失效函数的计算算法
