数据结构-KMP算法的实现

数据结构 课程设计报告

设计题目：模式匹配中的KMP算法的实现

专业：计算机科技 院系：计算机学院 姓名：xxxxxxxx 学号：xxxxxxx

时间：2013年9月22日

1

目 录

1 需求分析 ............................................................. 3

1.1 问题描述 .................................................................................................................... 3 1.2 基本要求 .................................................................................................................... 3 2 概要设计 ............................................................. 3 3 详细设计 ............................................................. 5

3.1 为主串和模式串赋值 ......................................................................................... 5 3.2 利用Output（）函数输出串。 ................................................................... 55 3.3 求各串的长度 ......................................................................................................... 6 3.4 求模式串的模式值next[]函数 ...................................................................... 6 3.5 模式匹配KMP算法的实现： ...................................................................... 7 4 测试与分析 ........................................... 7 5 总结 .................................................................. 9 6 附录：源程序清单 .................................................. 9 参考文献 ............................................................... 13

2

1 需求分析

1.1 问题描述

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.2 基本要求

用C编写一个程序实现模式匹配的KMP算法。要求对于任何输入串A，实现算法求next 函数值；利用next函数值，实现串A在串B中的定位；若未搜索到，就返回0。 首先要从键盘输入主串B和模式串A，并采用用链式存储，再根据Next( )函数求模式串的Next值，利用KMP 算法进行匹配，再用输出函数输出结果！

2 概要设计

对该kmp 算法，定义的抽象数据类型如下：

ADT String{

数据对象：D={ai|ai∈CharacterSet,i=1,2,3,?,n,n≥0} 数据关系：R1={|ai-1,ai∈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个字符

3

之后第一次出现的位置；否则函数值为0。

DestoryString(&S) 初始条件：串S存在。 操作结果：串S被销毁。 }ADT String

该算法是对串进行操作，对串的存储结构用线性表的链式存储结构表示： typedef struct LString{ char data；

struct LString *next； }LString；

该算法分为三个模块：第一模块[Input( )函数]（利用该函数输入主串和模式串）；第二模块[Output( )函数利用该函数输出串）。第三模块[Length（）]（利用该函数求各串的长度）；第四模块[Get_next( )函数]（利用该函数求出模式串的next函数值）；第五模块[Index_KMP（）函数]（利用该函数进行主串和模式串之间的匹配）；各个模块之间的调用关系如下图所示：图2.1是对整个函数的流程图。

开始 输入A，B，pos A ，B 调用Input函数存储 调用 Get_next函数 调用Index_KMP 函数， 并用Loc接收函数值 调用Output输出A，B， 输出LOC，Next 结束

整个函数的流程图

对A,B执行Length函数

4