模式匹配中的KMP算法的实现

数据结构课程设计

设计说明书

模式匹配中的KMP算法的实现

学生姓名 学班成

号 级 绩

高 虹 ********** 专升本1101

魏 佳

指导教师

计算机科学与技术系 2011年 9 月 9 日

数据结构课程设计评阅书

题 目 模式匹配中的KMP算法的实现 学生姓名 高虹 指导教师评语及成绩 学号 1118042026 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。

课程设计任务书

2011—2012学年第一学期

专业： 计算机科学与技术 学号： 1118042026 姓名： 高虹 课程设计名称： 数据结构课程设计 设 计 题 目： 模式匹配中的KMP算法的实现 完 成 期 限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周 设计内容：

用C/C++编写一个程序实现字符串的查找。要求使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提示。 设计要求:

1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）条件是什么？确定问题的输入数据集合。

2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；

3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；

4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；

5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；

6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；

7）编写课程设计报告；

以上要求中前三个阶段的任务完成后，先将设计说明数的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。

指导教师（签字）： 教研室主任（签字）： 批准日期： 2011年 8月 29 日

摘 要

本次课程设计通过使用KMP算法将模式匹配算法进行了简化。这种算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特—莫里斯—普拉特操作（简称为ＫＭＰ算法）。此算法可以在Ｏ（ｎ＋ｍ）的时间数量级上完成串的模式匹配操作。通过使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提示。 关键字：KMP算法；模式匹配；待查找文本

目 录

1课题描述 .................................................................. 1 2问题定义和任务分析 ........................................................ 2 3逻辑设计 .................................................................. 3 4详细设计 .................................................................. 6 5程序编码 .................................................................. 7 6程序调试与测试 ............................................................ 9 7结果分析 ................................................................. 10 8总结 .................................................................... 12 参考文献 .................................................................. 13

1课题描述

字符串子串在原串中的定位操作通常称为字符串的模式匹配，是各种传处理系统中最重要的操作之一。字符串定位字串的方法比较多，这里实现用KMP算法来实现模式穿的匹配，给出模式串，要求程序求出其Next[j]。KMP匹配算法高效的部分就是此次匹配失败后下次比较开始位置的确定，这样每次平均移动的字符就不止一个，大大减少了循环的次数，而且比较指针没有回调，提高了效率。设计思想：这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个发生匹配不成功的情况时,应该从模式字符串的第k + 1个字符开始新的匹配。

1

2问题定义和任务分析

本课设要求使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提示。KMP算法是模式匹配的一种模式匹配算法的升级。其改进在于每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。KMP匹配算法高效的部分就是此次匹配失败后下次比较开始位置的确定，这样每次平均移动的字符就不止一个，大大减少了循环的次数，而且比较指针没有回调，提高了效率。

2

通过对课题的分析设计，画出程序流程图，如图1.1所示。

图1.1 程序流程图

3

3逻辑设计

在此程序中调用了Index_KMP(S,T,x)函数，Index_KMP(S,T,x)函数的流程图如图1.2所示。

图1.2 Index_KMP(S,T,x)函数流程图

4

在Index_KMP(S,T,x)函数的流程图中又调用了GetNext(T,next)函数，GetNext(T,next)函数流程图如图1.3所示。

图1.3 GetNext(T,next)函数流程图

5

4详细设计

在模式匹配中的KMP算法的实现的函数中主函数先定义主串S、模式串T和x，并设两字符串的长度为为s和t，赋值为0，再分别求得两字符串的长度，最后调用Index_KMP(S,T,x)函数，求得匹配位置。

在Index_KMP(S,T,x) 函数中，先定义next[200]数组，定义i、j并赋值为0，接下来调用GetNext(T,next)函数，通过循环判断条件i=t条件判断语句，如果成立，执行x=i-t+1；如果不成立，则执行x=-1。

函数GetNext(T,next)的作用是求得模式串T的next函数值并存入数组next。先定义j和k，并给j赋值为0,k赋值为-1,next[0]赋值为-1，再通过循环判断j6

5程序编码

模式匹配中的KMP算法的实现程序代码如下所示： #include #include #include #include #include #define MAX 200

using namespace std;

char S[MAX],T[MAX]; int s = 0,t = 0;

void GetNext(char *T,int *next)//求模式串T的next函数值并存入数组next { int j,k; j = 0,k = -1,next[0] = -1; while(jint Index_KMP(char *S,char *T,int &x)

//利用模式串T的next函数求T在主串S中第x个字符之后的位置的KMP算法。其中T非空，17

while(i=t)//匹配成功 x = i-t+1; else x = -1; return 1; }

int main()//主函数 { int x; printf(\"Please Input The String Of S:\\n\"); gets(S); printf(\"\\n\"); printf(\"Please Input The String Of T:\\n\"); gets(T); printf(\"\\n\"); s = strlen(S); t = strlen(T); Index_KMP(S,T,x); printf(\"The String Start at %d\\n\ system(\"pause\"); return 0; }

8

6程序调试与测试

（1）在Index_KMP函数中，要返回利用return返回一个有用的值，如图2.1所示。

图2.1 return返回值

当删除return返回值，则程序出错，如图2.2所示。

图2.2 删除return返回值

（2）在GetNext函数中，给数组next中的next[0]赋值为-1，如图2.3所示。

图2.3 next[0]赋值为-1

当其改为0时，出现函数无法运行的结果，如图2.4所示。

图2.4 改后程序运行结果

9

7结果分析

运行模式匹配中的KMP算法的实现的程序，当找到匹配的字符串的位置时，运行结果如图3.1所示。

图3.1 找到匹配字符位置

10

运行模式匹配中的KMP算法的实现的程序，当没找到匹配的字符串的位置时，返回值为-1，运行结果如图3.2所示。

图3.2 没有找到匹配位置

11

8总结

通过此次模式匹配中的KMP算法的实现的课设，我认识到自己在以前的课程学习中还有很多的不足。在课设中，我了解到各种算法对软件设计的重要性，它能帮助程序设计者设计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发挥了重要作用。这次课设让我对C语言又复习了一遍。

此次课设已经结束，但我不会结束对数据结构和C语言的学习。很高兴能和同学们一起完成模式匹配中的KMP算法的实现的课设，谢谢老师的帮助，也谢谢我的同学们。

12

参考文献

[1] 严蔚敏,吴伟民. 数据结构(C语言版). 北京：清华大学出版, 2008 [2] 朱素英, KMP模式匹配算法的探讨.浏览网,2007 [3] 侯识忠,数据结构算法.北京：中国水利水电出版社,2005

[4] 胡明,模式匹配KMP算法中求next数组的算法.长春工业大学计算机科学与工程学院,2007 [5] 张海藩.软件工程（第五版）.北京:人民邮电出版社，2010

13