没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构课程设计实验报告-KMP算法的实现
KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是:从主串的S的第POS个字符开始起和模式的第一个字符比较之,如相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较之。以此类推,直到模式T中的每个字符依次和主串S中的一个连续字符序列相等,则称匹配成功,则函数值为和模式T中的第一个字符相等的字符在主串S中的序号,否则称匹配不成功,函数值为0.而对于模式匹配的KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进过程在于:每当一趟匹配过程出现字符比较不相等时,不需回溯i指针,而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后,继续进行比较。滑动的这一段距离我们将会用到函数Next[], KMP算法的最大特点是指示主串的指针不须回溯,整个匹配过程中,对主串仅需从头到尾扫描一遍,这对处理从外设输入的庞大文件很有效,可以边度入边匹配,而无需回头重读。 开发工具:C语言
资源详情
资源评论
资源推荐
1
数据结构
课程设计报告
设计题目:模式匹配中的
KMP
算法的实现
专业:计算机科技
院系:计算机学院
姓名: xxxxxxxx
学号: xxxxxxx
时间:2013 年 9 月 22 日
2
目 录
1 需求分析........................................................................................ 2
1.1 问题描述...............................................................................................................................2
1.2 基本要求...............................................................................................................................3
2 概要设计........................................................................................ 3
3 详细设计:......................................................................................4
3.1 为主串和模式串赋值...........................................................................................................4
3.2 利用 Output()函数输出串。...........................................................................................5
3.3 求各串的长度.......................................................................................................................6
3.4 求模式串的模式值 next[]函数............................................................................................6
3.5 模式匹配 KMP 算法的实现:............................................................................................7
4 测试与分析......................................................................................8
5 总结..............................................................................................9
通过此次模式匹配中的 KMP 算法的实现的课设,我认识到自己在以前的课程学习中还有
很多的不足。在课设中,我了解到各种算法对软件设计的重要性,它能帮助程序设计者设
计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发
挥了重要作用。这次课设让我对 C 语言又复习了一遍。......................................9
6 附录:源程序清单..............................................................................9
1 需求分析
1.1 问题描述
KMP 算法是对一般模式匹配算法的改进,由 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同
时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为 KMP 算法)。
对于一般的模式匹配算法:分别利用两个指针 i 和 j 指示主串 S 和 T 中的当前正待比较
的字符位置。算法的基本思想是:从主串的 S 的第 POS 个字符开始起和模式的第一个字符
比较之,如相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的
字符比较之。以此类推,直到模式 T 中的每个字符依次和主串 S 中的一个连续字符序列相
3
等,则称匹配成功,则函数值为和模式 T 中的第一个字符相等的字符在主串 S 中的序号,
否则称匹配不成功,函数值为 0.而对于模式匹配的 KMP 算法可以在 O(n+m)的时间数量
级上完成串的模式匹配操作。其改进过程在于:每当一趟匹配过程出现字符比较不相等时
不需回溯 i 指针,而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的
距离后,继续进行比较。滑动的这一段距离我们将会用到函数 Next[],
KMP 算法的最大特点是指示主串的指针不须回溯,整个匹配过程中,对主串仅需从头
到尾扫描一遍,这对处理从外设输入的庞大文件很有效,可以边度入边匹配,而无需回头
重读。
开发工具:C 语言
1.2 基本要求
用 C 编写一个程序实现模式匹配的 KMP 算法。要求对于任何输入串 A,实现算法求
next 函数值;利用 next 函数值,实现串 A 在串 B 中的定位;若未搜索到,
就返回 0。 首先要从键盘输入主串 B 和模式串 A,并采用用链式存储,再根据 Next( )函
数求模式串的 Next 值,利用 KMP 算法进行匹配,再用输出函数输出结果!
2 概要设计
对该 kmp 算法,定义的抽象数据类型如下:
ADT String{
数据对象:D={a
i
|a
i
∈CharacterSet,i=1,2,3,…,n,n≥0}
数据关系:R1={<a
i
-1,a
i
>|a
i
-1,a
i
∈D,i=2,…,n}
基本操作:StrAssign(&T,chars)
初始条件:chars 是字符串常量。
操作结果:生成一个其值等于 chars 的串 T。
StrCopy(S)
初始条件:串 S 存在。
操作结果:若 S 为空串,则返回 TRUE,否则返回 FALSE。
StrLength(S)
初始条件:串 S 存在。
操作结果:返回 S 元素的个数,成为串的长度。
Index(S,T,pos)
初始条件:串 S 和 T 存在,T 是非空串,1≤pos≤StrLength(S).
操作结果:若主串 S 中存在和串 T 相同的子串,则返回他在主串 S 中的第 pos 个字
符之后第一次出现的位置;否则函数值为 0。
DestoryString(&S)
初始条件:串 S 存在。
操作结果:串 S 被销毁。
}ADT String
该算法是对串进行操作,对串的存储结构用线性表的链式存储结构表示:
typedef struct LString{
剩余12页未读,继续阅读
T_EyE
- 粉丝: 6
- 资源: 19
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0