字符串匹配算法的研究及其程序实现计算机学院计算机科学与技术专业2007级指导教师：滕云摘要：在字符串匹配算法之中，最古老和最著名的是由D. E. Knuth, J. h. Morris, V. R. Pratt 在1997年共同提出的KMP算法。

直至今日，人们对字符串匹配问题还在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法;学者们在不同的研究方向上，设计出了很多有效的匹配算法。

在现实生活中，串匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。

在许多应用系统中，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统的性能。

该论文重点分析了KMP算法的实现原理和C语言实现，并在此基础上提出了改进的KMP算法，使得该算法更方便实用。

关键词：KMP算法；时间复杂度；串匹配；改进；方便使用；String matching algorithm and Implementation of the Program College of Computer Sciences, Computer Science and Technology Professionalgrade 2007, Instructor YunTengAbstractor:Among the string matching algorithm,the oldest and most famous is KMP algorithm co-sponsored by D.E Knuth, J. h. Morris, VR Pratt in 1997. As of today, a lot of research to String matching are still in progress, to seek a more simply or better average time complexity of the algorithm. In different research direction, scholars have designed a lot of valid matching.In real life, the string matching technique is widely used，The main areas include: intrusion detection, virus detection, information retrieval, information filtering, computational biology, financial inspection and so on.In many applications，a large percentage of the time was placed by the string matching, so the string matching algorithms significantly affect the speed performance of the whole system.The paper analyzes the implementation of the KMP algorithm theory and through the C language to achieve it.And we puts forward a modified KMP algorithm in order to makes the algorithm more convenient and practical.Key words:KMP algorithm; Time complexity; String matching; Improved; Easy to use;目录摘要﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒ 1 ABSTRACT﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒ 1第一章引言﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒ 3第一节：字符串匹配研究的目的和意义﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒3第二节：本文的内容和安排﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒ 3第二章串匹配算法的概念与研究现状﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒ 4第一节：字符串匹配的有关概念﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒4第二节：字符串匹配算法的研究现状﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒4第三章KMP算法和BM算法及其改进算法的研究及实现﹒﹒﹒﹒﹒﹒5 第一节：KMP算法的研究及实现﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒5第二节：KMP算法改进及其程序实现﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒8第四章总结和展望﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒12 第一节：总结﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒13第二节：展望﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒13参考文献﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒14致谢﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒14第一章：引言第一节：字符串匹配研究的目的和意义字符串是计算机科学中常见的基本概念，搜索问题也是计算机科学中的基本问题。

而且迄今为止文本信息仍然还是最主要的信息交换手段之一，因此作为文本处理中的一个重要领域——字符串匹配，就显得尤其的重要，随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在；在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。

本文力图阐明字符串匹配算法的发展过程中的两个重要的算法KMP算法和BM算法，并且并介绍了各个算法的特点，并给予了适当的比较和分析，进而提出了新的字符串匹配算法希望能够在各方面有所改进。

字符串匹配技术有着十分广泛的应用领域，它的最直接的应用领域是构建数据的全文检索系统和图书文献目录摘要的查询系统。

尤其在近年来，网络技术马不停蹄的快速发展，网络带宽不断增加，随之出现的问题也越来越多，加之随着网络技术和生物技术的不断发展，串模式匹配技术又在网络安全，网络信息检索和生物计算等领域中发挥着重要作用，并不断发展。

而且在对大量黄色信息，反动言论和国家机密的过滤方面以及入侵检测技术和内容过滤技术方面字符串匹配算法也扮演者一个不可或缺的角色。

随着生命科学技术的发展，人们对生命物质的微观结构的认识越来越清晰。

而且人类基因组序列的绘制工作目前己经完成。

计算生物学中的一个最基本问题是，寻找一个或一组基因片断在一个基因序列中的出现位置，以比较基因的相似性和遗传关系；或者根据己知的蛋白质样本去匹配未知的蛋白质序列，来确定这种未知的蛋白质序列所属蛋白质的种类和功能。

由于蛋白质和基因都可以使用建立在一定字符集上的符号序列来表示，因而传统的字符串匹配技术又有了新的发挥之地。

尤其是近些年来的发展，科学家们对基因发生的突变和进化等变化进行研究，来描述同一物种的基因序列可能存在一定的差别，所以这就促进了“近似匹配”技术的又一提高和发展。

综上所述，字符串匹配技术在众多的领域中发挥着基础的核心作用，对字符串匹配算法作进一步的研究和改进，对于提高执行的效率、增加应用系统的性能、节约硬件成本等有着重要的现实意义。

第二节：本文的内容和安排本文通过对经典字符串匹配算法的深入理解和分析，在KMP算法的基础上提出了两种改进算法，并且给出了程序实现代码，经过分析和测试确定其性能得到提高，在某些方面都达到了较高的水平。

本文的后续的章节安排为：第二章将对字符串匹配算法的概念进行归纳并总结其研究现状；第三章详细分析字符串匹配算法：KMP算法，并提出相应的新的改进算法，而且深入分析所涉及到的经典算法的思想以及程序的实现方法，并且将改进后的算法与之比较，得出改进后算法的优点。

最后第四章进行总结和展望。

第二章串匹配算法的概念与研究现状第一节：字符串匹配的有关概念字符串是n ( 0 ) 个字符的有限序列，记作 S : “c0c1c2…cn-1”。

其中，S是串名字；“c0c1c2…cn-1”是串值；ci是串中字符；n是串的长度。

如：“Welcome to Linux world ”模式匹配是串的基本运算之一。

它是指在串中寻找子串（第一个字符）在串中的位置。

有两个字符串T和Ｓ，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。

一旦模式S在正文T中找到，就说发生一次匹配。

有些应用可能会要求找出所有的匹配位置。

算法复杂度分为时间复杂度和空间复杂度。

其作用：时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。

KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。

简单匹配算法的时间复杂度为O(m*n);KMP匹配算法的时间复杂度为O(m+n).第二节：字符串匹配算法的研究现状近年来，学术界的兴趣与日俱增，特别在生物信息学和信息检索两个领域中，需要处理的文本规模越来越大，而且需要在文本中进行越来越复杂的搜索。

因此，出现了一种非标准的模式匹配问题,该问题涵盖的内容包括通配符、近似匹配等等。

近期，学术界最活跃的问题之一就是研究带有通配符的串匹配问题。

即带有don't care或wildcard字符。

然而，通配符的引入会让问题定义更加灵活，却也带来了复杂性。

算法的设计有时不仅仅考虑时空效率，保证匹配结果的完备性很可能成为算法设计更重要的问题。

在串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。

另外，随着新一代计算机的产生，会出现一些新技术，例如位并行等。

然而KMP算法依然占据着不可替代的作用，尤其是他们的优化版更是应用广泛。

第三章：KMP算法和BM算法及其改进算法的研究及实现第一节：KMP算法的研究及实现KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法（Brute-Force，最基本的字符串匹配算法的）改进。

由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。

next 函数包含了模式串本身局部匹配的信息。

首先，我们引入一个叫失败链接值(faillink)的概念，就是说“每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的‘部分匹配’结果（匹配串的每个字符的失败链接值）将模式（匹配子串）向右‘滑动’尽可能远的一段距离，继续进行比较。

”其实质失败链接值就是一个和主串完全无关只和子串相关的值。