中北大学软件学院
实验报告
专 业:_________________________ 方 向:_________________________ 课程名称:_________________________ 班 级:_________________________ 学 号:_________________________ 姓 名:_________________________ 辅导教师:_________________________
2016年3月制
参11考 1
成绩:
实验时间 1.实验名称 2016年4月7日8时至10时 学时数 2 实验一 串匹配程序设计 2.实验目的 (1) 熟练掌握串匹配的含义 (2) 掌握BF算法匹配的过程并编程实现 (3) 熟悉C++编译环境的基本操作 3.实验内容 给定两个字符串S和T,用BF算法,在主串S中查找字串T,输出结果,输出时要求有文字说明。请编写程序。 4.实验原理或流程图 基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹配的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。 设串S长度为n,串T长度为m,在匹配成功的情况下,考虑最坏情况,即每趟不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处,则在i-1趟不成功的匹配中共比较了(i-1)×m次,第i趟成功的匹配共比较了m次,所以总共比较了i×m次,因此平均比较次数是: n?m?1?i?1pi?(i?m)?n?m?1?i?11n?m?1?(i?m)?m(n?m?2)2 最坏情况是O(n×m)。 或者写书上P39页的伪代码描述。 参11考 2
5.实验过程或源代码 #include
3
中北大学软件学院算法实验报告(附截图)(优选借鉴)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)