文档介绍：编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
实验报告一 串匹配问题 
班级：_计算机师 _ 学 号： 2 姓 名：_
一、实验题目：给定一个文本, 在该文本中查找并定位任意给定字符串。
实验目的：
(1) 深刻理解并掌握蛮力法的设计思想;
(2) 提高应用蛮力法设计算法的技能;
(3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进展一定程度的改进, 改进其时间性能。
三、实验要求：
(1) 实现 BF算法;
(2) 实现 BF算法的改进算法: KMP 算法和 BM 算法;
(3) 对上述3个算法进展时间复杂性分析, 并设计实验程序验证分析结果。
算法描述〔对算法主要局部进展伪代码描述或画出流程图〕
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右移的计算方法却发生了较大的变化。
编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
  开场
主串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-NM-Nm-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
 
编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
开场
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算法
完毕
0→a
0→b
0→z
模式T长度-1→i
i+DIST(T,S[i])→i