数据结构第4章.pptVIP

串的模式匹配定义在主串中寻找子串（第一个字符）在串中的位置词汇在模式匹配中，子串称为模式，主串称为目标。示例目标T:“Beijing”模式P:“jin”匹配结果=3朴素的模式匹配（B-F算法）第1趟Tabbaba Paba 第2趟 Tabbaba Paba i=2j=2i=1j=0第3趟Tabbaba Paba 第4趟 Tabbaba Paba i=2j=0i=6j=3朴素的模式匹配算法intAString::Find(AStringpat,intk)const{//在当前串中从第k个字符开始寻找模式pat在当//前串中匹配的位置。若匹配成功,则函数返回首//次匹配的位置,否则返回-1。inti,j,n=curLength,m=pat.curLength;for(i=k;i=n-m;i++){ for(j=0;jm;j++)if(ch[i+j]!=pat.ch[j])break;//本次失配if(j==m)returni;//pat扫描完,匹配成功 } return-1; //pat为空或在*this中找不到它};在最坏情况下，若设n为目标串长度，m为模式串长度，则匹配算法最多比较n-m+1趟，每趟比较都在比较到模式串尾部才出现不等，要做m次比较，总比较次数将达到(n-m+1)*m。在多数场合下m远小于n，因此，算法的运行时间为O(n*m)。低效的原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配只要消除了每趟失配后为实施下一趟比较时目标指针的回退，可以提高模式匹配效率。这种处理思想是由D.E.Knuth、J.H.Morris和V.R.Pratt同时提出来的，故称为KMP算法。实施KMP算法的时间代价：若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=n。若每趟第m个不匹配，总比较次数最坏亦达到n。目标T t0t1t2……tm-1…tn-1 ???? 模式pat p0p1p2……pm-1 目标T t0t1t2……tm-1tm…tn-1 ????模式pat p0p1……pm-2pm-1目标T t0t1……titi+1……ti+m-2ti+m-1…tn-1 ‖‖‖‖模式pat p0p1……pm-2pm-1改进的模式匹配Tt0t1…ts-1tsts+1ts+2…ts+j-1ts+jts+j+1…tn-1‖‖‖‖‖?P p0p1p2…pj-1pj则有tsts+1ts+2…ts+j-1=p0p1p2…pj-1(1)下一趟，为使模式P与目标T匹配，必须满足p0p1p2…pj-1…pm-1=ts+1ts+2ts+3…ts+j…ts+m如果p0p1…pj-2?p1p2…pj-1 (2)则立刻可以断定 p0p1…pj-2?ts+1ts+2…ts+j-1下一趟必不匹配p0p1…pj-2同样，若 p0p1…p