串匹配问题(共9页).doc

精选优质文档-倾情为你奉上实 验 报 告实验项目：_ 串匹配问题_班级：_计算机_ 姓 名：_一、实验题目：给定一个文本, 在该文本中查找并定位任意给定字符串。 2、 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求： ( 1) 实现 BF 算法; (2 ) 实现 BF 算法的改进算法: KMP 算法和 BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证分析结果。 4、 算法描述（对算法主要部分进行伪代码描述或画出流程图）BF算法：基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复