数据结构与算法设计PPT (12).pdf
《数据结构与算法设计PPT (12).pdf》由会员分享,可在线阅读,更多相关《数据结构与算法设计PPT (12).pdf(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第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-
2、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
3、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比较时不相等发现失败时:从
4、当前位置开始,和模式串中的第二个字符比较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
5、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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法设计PPT 12 数据结构 算法 设计 PPT 12
限制150内