实验报告一串匹配问题
班级：_计算机师_学号：2姓名：_
一、实验题目：给定一个文本在该文本中查找并定位任意给定字符串。二、实验目的：
1深刻理解并掌握蛮力法的设计思想2提高应用蛮力法设计算法的技能3理解这样一个观点用蛮力法设计的算法一般来说经过适度的努力后都可
以对算法的第一个版本进行一定程度的改良改进其时间性能。三、实验要求：1实现BF算法2实现BF算法的改进算法KMP算法和BM算法3对上述3个算法进行时间复杂性分析并设计实验程序验证分析结果。四、算法描述（对算法主要部分进行伪代码描述或画出流程图）BF算法：
基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是
m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。KMP算法：
基本思想：1在串S和串T中分别设比较的起始下标i和j；2循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
21如果SiTj，则继续比较S和T的下一个字符；否则22将j向右滑动到
extj位置，即j
extj；23如果j0，则将i和j分别加1，准备下一趟比较；24如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；BM算法：基本思想：BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。
f开始
主串S长
模度式→Tm长
度0→→i
NimY0→b
i→a
NSaT
b且bYa≠加
1
b加1
Yb
N结束
BF算法
开始
主串S长
度→m
0→a模式T长
N
0→b度a→

YMN
NSMaNT
Ybm且
ba≠加
1
b加1
Yb

N

extb→b
ab→a
Y
结
b1
束
N
b加1
KMP算法
f开始
0→a
0→b0→z
模式T长N
i度主1→串iS
Y长度1模式T长
度1→j
j0且
N
SiTYi减j1
j减1
Y
N
j0
iDISTT
结Si→i束BM算法
五、实验结果与结论：（给出测试数据以及程序运行结果，并进行比较，得出自己的结论）
设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后
f缀规则，来计算模式串向右移动的距离，直到整r