模式匹配的KMP算法

1、模式匹配的KMP算法学生姓名：侯成龙 指导老师：罗心摘要本课程设计主要解决用模式匹配的KMP算法进行字串定位的程序设计。在本课 程设计中，系统开发平台为Windows XP,程序设计设计语言采用Visual C+6.0,程序运 行平台为Windows 98/2000/XP。在程序设计中，采用了串的KMP模式匹配算法实现了子 串的定位操作。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以 解决实际问题。关键词 程序设计；串的模式匹配；KMP算法；Visual C+6.01引言子串定位运算通常称为串的模式匹配或串匹配运算，是串处理中最重要的运算之一， 应用非常广泛1。本课程设计主要

2、解决用模式匹配的KMP算法进行字串定位的程序设计。1.1课题背景计算机上的非数值处理的对象基本上是字符串数据。在较早的程序设计语言中，字符 串是作为输入和输出的常量出现的。随着语言加工程序的发展，产生了字符串处理。这样， 字符串也就作为一种变量类型出现在越来越多的程序设计语言中，同时也产生了一系列字 符串的操作。字符串一般简称为串。在汇编和语言的编译程序中，源程序及目标程序都是 字符串数据。在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般 也是作为字符串处理的。又如信息检索系统、文字编辑程序、问答系统、自然语言翻译系 统以及音乐分析程序等，都是以字符串数据作为处理对象的我数据

3、结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构 分为逻辑结构和存储结构。数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的 整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关 系的不同，数据结构分为四类：集合；线性结构；树结构；图结构。数据的逻辑结构属于 用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常 常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称为物理结构，是 数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或

4、显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结 构。串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为s =a1a2an(n=0。其中，s是串的名，用单引号括起来的字符序列是串的值；ai可以是 字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串，他的 长度为零。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称 为主串。通常称字符在序列中的序号为该字符串在串中的位置。子串在主串中的位置则以 子串的第一个字符在主串中的位置来表示。类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在

5、 串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的 存储区，则可以用定长数组来描述之。子串定位运算通常称为串的模式匹配或串匹配运算，是串处理中最重要的运算之一， 应用非常广泛。例如，在文本编辑程序中，我们经常要查找某个特定单词在文本中出现的 位置。显然解决该问题的有效算法能极大地提高文本编辑程序的响应性能囹。在计算机科学领域，串的模式匹配算法一直都是研究焦点之一。串匹配从方式上可分 为精确匹配、模糊匹配、并行匹配等，KMP算法是字符串查找算法中的一个经典算法， 该算法在最坏情况下具有线性的查找时间，查找效率高。1.2课程设计目的子串定位就是要在主串s中找到一个与子

6、串t相同的子串。通常我们把主串s称为目 标串，把子串t称为模式串，把从目标串s中查找t子串的定位过程称为串的“模式匹配”。 模式匹配有两种结果：若从主串s中找到模式为t的子串，则返回t子串在s中的起始位 置。当s中有多个模式匹配为t的子串时，通常只找出第一个子串的起始位置，这种情况 称为匹配成功，否则称为匹配失败6。本课程设计主要是用模式匹配的KMP算法实现子串的定位操作，通过程序的编写、调 试和运行可以进一步掌握数据结构及算法的程序实现的基本方法。理解子串定位操作的实 现过程以及KMP算法对基本模式匹配算法的改进之处。1.3课程设计内容本课程设计主要完成改进基本的模式匹配算法，运用KMP算法

7、实现串的模式匹配的 程序设计。例如，运行改进后程序时，输入主串s= addabbcgsa”，模式串t=abbc”时， 显示模式匹配成功，模式串在主串的位置从第 4个字符开始；如果输入输入主串s= “addabbcgsa”，模式串t=absc”时，则显示模式匹配不成功，在主串中未找到模式串。2设计思路与方案2.1设计思路注意到模式匹配的KMP算法是对模式匹配简单算法改进后的算法，所以有必要先介 绍简单模式匹配算法及其基本思想，进而提出一种改进后的模式匹配算法-KMP算法。因 为KMP算法是在已知模式串的next函数值的基础上执行的，所以又要先实现求模式串next 函数值的算法。2.2设计方案在本

8、课程设计中，运用串的模式匹配的KMP算法进行子串的定位操作，要实现这一过 程主要用到以下函数：求next函数值的算法：void GetNext(char TMAXSTRLEN,int (&next)64)计算next函数修正值的算法：void GetNextVal(char TMAXSTRLEN,int (&next)64)KMP算法：int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (&next)64,int pos) 主函数：void main()3详细实现3.1模式匹配的基本算法采用定长顺序存储结构，可以写出不依赖于其他串操作的基本匹配算法

9、。该算法的基 本思想是：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个 比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至 模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为 和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零。 算法如下：int Index(SString S,SString T,int pos) 返回子串T在主串S中的第pos个字符之后的位置的。若不存在，则函数值为0。其中，T 非空，1忍pos 忍 StrLength(S)。int i=pos; int j=1;wh

10、ile (i=S0&jT0) return i-T0;else return 0;/ Index3.2模式匹配的改进算法KMP算法这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP 算法。此算法可以在O(n+m)的时间内数量级上完成串的模式匹配操作。其改进之处在于： 每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部 分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较KMP算法如 下：int Index_KMP(SString S,SString T,int (&nextval)64,int p

11、os) 利用模式串T的next函数T求T在主串S中的第pos个字符之后的位置的/ KMP 算法。其中，T 非空，1忍pos忍StrLength(S)。int i=pos; int j=1;while (i=S0&jT0) return i-T0;else return 0;/ Index_KMP模式串的next函数的定义：0,当二1时nest j = Max k | j且 pi. . . pLri = pj-ld-i. . . pj-iL ，其他情况例如：P=abaabcac 则12345678neKt j:01122312 73.3模式串next函数值的算法及next修改值的算法KMP算法是

12、在已知模式串的next函数值的基础上执行的，求next函数值的算法如下 所示：void get_next(SString T, int next ) 求模式串T的next函数值并存入数组next。i=1; next 1=0;j=0;while(iT0) if (j=0|Ti=Tj) +i; +j;next i=j;else j=nextj;/get_next以上定义的next函数在某些情况下尚有缺陷。进行修正，可得计算next函数修正值的 算法如下(此时匹配算法不变)：void get_nextval(SString T, int (&nextval)64) 求模式串T的next函数修正值并存

13、入数组 i=1; nextval1=0;int j=0;while(iT0) if (j=0|Ti=Tj) +i； +j；if (Ti!=Tj) nextvali=j;else nextvali=nextvalj;else j=nextvalj;/get_nextval3.4程序运行过程将以上主要函数加以主函数写出完整的C语言代码，在Visual C+6.0中运行。本操作 的流程图如下所示：图3-14运行环境与结果4.1运行环境在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C+6.0,程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个

14、版本:学习版、专业版和企业版， 不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课 程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是 Microsoft 公司的 Microsoft Visual Studio 6.0开发工具箱中 的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和 为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后， 随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。Visual

15、 C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界 面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以 及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性， 只适用于 Windows 2000,Windows XP和 Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化 编程环境。Visual

16、 C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活 性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而 出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化 开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用 户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运 行、调试应用程序。4.2运行结果(1)在程序开始运行时，提示输入主串S，如下图4-1所示.c土 D:CCISDev98BinDeb

17、ugCpp1. exeGetNext-IndexKMPJn：输入主串E(2)在输入主串s= “addassdaffd”后，提示输入模式串t,结果如下图4-2所示:图4-2(3)输入模式串t=assd”，结果如下图4-3所示:(4)回车，显示结果。如下图4-4所示:图4-4(5)若模式输入t= “asss”。如下图4-5所示:(6)回车，显示结果，如下图4-6所示:5结束语这次的课程设计的内容是用模式匹配的KMP算法进行子串的定位操作，这对我来说是 个很具有挑战性的任务，虽然只做了一个很简单的模式匹配程序，但通过两个星期的设计 也从中学到了不少东西，更深刻的理解了课本中的内容。数据结构是一门实践

18、性较强 的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻 理解了串的概念及其基本操作，尤其是串的模式匹配算法。根据实际问题的需要，对个方 面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了 理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的， 良好的程序设计技能。提高综合运用所学知识的能力。通过这次课程设计，我深谙创新的重要性，它是当代大学生必备的基本素质之一。模 式匹配的KMP算法是一种改进的模式匹配算法，之所以要改进，是因为它较以前模式匹 配的朴素算法有更高的效率和完整性，更适合实际程序开发的需要。在这次课

19、程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这 次的课程设计，在此，我忠心感谢我的指导老师一一罗心。罗老师对工作认真负责，耐心 辅导，知识丰富。在这次课程设计中给了我很大的帮助。他严谨的治学精神和深厚的理论 水平都使我获益非浅。同时还要感谢我的同学，他们为我提出了很多有用的建议，帮助我 完成了这次的课程设计。最后也要感谢我们学校为我们提供良好的编程环境，使我们能够 按时完成任务。参考文献1田鲁怀.数据结构.北京：电子工业出版社，2006严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版,2008王红梅，胡明，王涛.数据结构（C+版）.北京：清华大学出版社，2007郑阿

20、奇，丁有和.Visual C+教程.北京：机械工业出版社，2006朱素英，李芝成.KMP模式匹配算法的探讨.浏览网， HYPERLINK /article/?NewID=CF364091-7F22-457F-9E2C-A35B020D4DF /article/?NewID=CF364091-7F22-457F-9E2C-A35B020D4DF :2007-5-28侯识忠，.数据结构算法.北京：中国水利水电出版社，2005胡明.模式匹配KMP算法中求next数组的算法.长春工业大学计算机科学与工程学院， HYPERLINK /sjjg/index.php?option=com_content&t

21、ask=view&id=706%ef%bc%9a /sjjg/index.php?option=com_content&task=view&id=706： 2007-7-18/字符串的模式匹配(KMP算法)#include#include#include#include#include#define MAXSTRLEN 64void GetNext(char TMAXSTRLEN,int (&next)64)int i,j;i=1;next1=j=0;while(i(int)T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;for(j=1;j(int)T0;

22、j+)printf(next%d=%-3d”,j,nextj);if( 5=0) printf(n);coutendl;void GetNext(char TMAXSTRLEN,int (&next)64,int m)int i,j;i=0;next0=-1;for(j=1;j=0) i=nexti;if(Tj=Ti+1) nextj=i+1;else nextj=-1;for(j=0;j=m;j+)printf(next%d=%-3d”,j,nextj);if(j+1)%5=0) printf(n);coutendl;void GetNextVal(char TMAXSTRLEN,int (

23、&next)64)int i,j;i=1;next1=j=0;while(i(int)T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj) nexti=j;else nexti=nextj;else j=nextj;for(i=1;i(int)T0;i+)printf(next%d=%-3d,i,nexti);if(i%5=0) coutendl;coutendl;int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (&next)64)int i,j,n,m;i=j=1;n=(int)S0;m=(int)T0;while(in|j=m)

24、 return i+1-m;else return 0;int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (&next)64,int pos)int i,j;i=pos;j=1;while(i(int)S0|j=(int)T0) return i+1-(int)T0;else return 0;int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (&next)64,int n,int m)int i,j;i=j=0;while(in&jm)if(Si=Tj) +i;+j;else if(j=0) i+;else j=nextj-1+1;if(jm) return -1;else return i-m+1;int IndexBF(char SMAXSTRLEN,char TMAXSTRLEN,int pos)int i,j;i=pos;j=1;while(i=S0&jT0) retur