字符串匹配算法：穷举、KMP、BM.ppt

《字符串匹配算法：穷举、KMP、BM.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章字符串字符串(String)字符串是n(0)个字符的有限序列，记作S:“c0c1c2…cn-1”其中，S是串名字“c0c1c2…cn-1”是串值ci是串中字符n是串的长度。如：“WelcometoShanghai!!!”在计算机非数值计算应用中，经常遇到字符序列的处理。如，文字编辑、情报检索、自然语言翻译、事务处理、图象处理等应用中经常遇到的那样。在计算机中，一个字符集上的每个字符用定长的代码表示，所有可能的各种字符都可以对应一个确定的代码。一个特定的字符序列称为字符串，简称为串。有两种方法能比较方便地表示一个字符串。一是人为地约定一个特殊的

2、代码为字符序列的结束符，每个字符串最后都有这个结束符。二是，为每个字符序列另引入一个整数，让该整数指出该字符串的字符个数。本书采用第一种表示字符串的方法模式匹配是串的基本运算之一。有两个字符串T和Ｓ，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。串的模式匹配定义在串中寻找子串（第一个字符）在串中的位置词汇在模式匹配中，子串称为模式，串称为目标。示例目标T:“Beijing”模式P:“jin”匹配结果=3记正文T的字符个数为n，令T=t0t

3、1t2…tn-1，记模式S的字符个数为m，令S=s0s1s2…sm-1。若正文中自位置k开始有一次匹配，则有sj=tk+j，0<=j

4、符串p比较*/for(i=0;i

5、ENT……模式patSTUDENT……目标TSTUDENSTUDENT……‖‖‖‖‖‖‖模式patSTUDENT简单模式匹配的缺点:无谓比较目标TFIFIFIYUDENT……‖‖‖‖模式patFIFIY目标TFIFIFIYUDENT……‖‖模式patFIFIY直接跳过错过成功比较目标TFIFIFIYUDENT……‖‖‖‖‖模式patFIFIY直接跳过子串可能错过成功比较穷举的模式匹配算法时间代价：最坏情况比较n-m+1趟，每趟比较m次，总比较次数达(n-m+1)*m原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检

6、测指针每趟不回退。改进的模式匹配(KMP)算法的时间代价：若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=n若每趟第m个不匹配，总比较次数最坏亦达到n7.2KMP算法目标Tt0t1t2……tj-1tj……tn-1‖‖‖‖X模式patp0p1p2……pj-1pj……pm-1目标Tt0t1…tk……tn-1模式patp0p1……pm-2pm-1改进的模式匹配：寻找最大“跳跃”Tt0…ts-1tsts+1ts+2…ts+j-1ts+jts+j+1…tn-1‖‖‖‖‖Pp0p1p2…pj-1pjpj+1则有tsts+1ts+2

7、…ts+j=p0p1p2…pj(1)为使模式P与目标T匹配，必须满足p0p1p2…pj-1…pm-1=ts+1ts+2ts+3…ts+j…ts+m如果p0p1…pj-1p1p2…pj(2)则立刻可以断定p0p1…pj-1ts+1ts+2…ts+j下一趟必不匹配同样，若p0p1…pj-2p2p3…pj则再下一趟也不匹配，因为有p0p1…pj-2ts+2ts+3…ts+j直到对于某一个“k”值，使得p0p1…pk+1pj-k-1pj-k…pj且p0p1…pk=pj-kpj-k+1…pj则p0p1…pk=ts+j-kts+j-k+1…ts+j‖‖

8、‖pj-kpj-k+1…pj因此，当正文T在t[j+i]比较失败时，正文t的扫视指针j不回溯，仍指向上一趟匹