BF算法、KMP算法、BM算法.doc

昆明理工大学信息工程与自动化学院学生实验报告
( 2010 — 2011 学年第一学期)
课程名称: 算法分析与设计开课实验室: 计算中心310 2010 年 11 月 12 日
年级、专业、班
计科081班
学号
200810405339
姓名
赵丽
成绩
实验项目名称
串匹配问题
指导教师
吴霖
教师评语
教师签名:
年月日
实验内容和目的
深刻理解并掌握蛮力算法的设计思想;
提高应用蛮力算法设计算法的技能;
理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。
实验原理及基本技术路线图(方框原理图)
串匹配问题——给定两个串S=“s1s2…sn”和T=“t1t2…tm”,在主串S中查找子串T的过程称为串匹配,也称模式匹配。
串匹配问题属于易解问题。
串匹配问题的特征:
(1)算法的一次执行时间不容忽视:问题规模 n 很大,常常需要在大量信息中进行匹配;
(2)算法改进所取得的积累效益不容忽视:串匹配操作经常被调用,执行频率高。
BF算法:
基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串
S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹配的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。
KMP算法:
1. 在串S和串T中分别设比较的起始下标i和j;
2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
如果S[i]=T[j],则继续比较S和T的下一个字符;否则
将j向右滑动到next[j]位置,即j=next[j];
如果j=0,则将i和j分别加1,准备下一趟比较;
如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回0;
BM算法:
BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左,但匹配发生失败时,模式T右移的计算方法却发生了较大的变化。
设计思想:设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较,若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则和好后缀规则,来计算模式串向右移动的距离,直到整个匹配过程的结束。  
开始
主串S长度→m
模式T长度→n
0→i
i<m
0→b
i→a
S[a]=T[b]且b≠n
a加1
b加1
b=n
Y
N
Y
Y
Y
N
N
N
BF算法
结束
开始
主串S长度→m
模式T长度→n
0→a
0→b
a≦m-n
S[a]=T[b]且b≠n
a加1
b加1
b=n
Y
Y
Y
N
N
N
KMP算法
结束
next[b]→b
a-b→a
b=-1
b加1
开始
i≦主串S长度-1
模式T长度-1→j
j≧0且S[i]=T[j]
i减1
j减1
j<0
Y
Y
Y
N
N
N
BM算法
结