资源描述：
《模式匹配的kmp算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、模式匹配的KMP算法研究学生姓名：黄飞指导老师：罗心摘要在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所冇出现。在本文屮主串表示为S二sls2s3・・・sn,模式串表示为T=tlt2-tmo$匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法冇BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它
2、做一些改进以及利用改进的KMP来实现多次模式匹配。关键字：模式匹配；主串；模式串；KMP算法ResearchandAnalysisofKMPPatternMatchingAlgorithmStudent:HuangfeiTeacher:LuoxinAbstractIncomputerscience,Stringpatternmatching(Hereinafterreferredtoasthestringmatching)algorithmisalwaysthefocusofthestudy.Inthespellcheck,langua
3、getranslation,datacompression,searchengine,thenetworkintrusiondetectionsystem,acomputcrvirussignaturematchingDNAsequencesandtheapplicationinthematch,matchedtostringmatching.Stringmatchingisinsearchofastringofpatternorallappear-Inthispaper,thestringisS=sls2s3…Sn,stringpat
4、ternforT=tit2...tm.Stringmatchingwaycanbedividedfromtheaccuratematching,fuzzymatching,parallelmatchingetc.,thefamousmatchingalgorithmsareKMPalgorithm,BFalgorithm,thealgorithmandsomeBMalgorithm.ThispaperinpreciseKMPalgorithmformatchingaspectsarediscussedandsomeimprovement
5、onitandusingtheimprovedKMPtorealizethemultipiepatternmatching.Keywords:patternmatching,Thestring;Patternstrings;KMPalgorithm1引言KMP算法是是对一般模式匹配算法的改进，由D.E.Knuth与V.R.Pmtt和J・H.Morris同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。对于一般的模式匹配算法：分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是：从主串的S
6、的第POS个字符开始起和模式的第一个字符比较之，如相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T屮的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在0(n+m)的吋间数量级上完成串的模式匹配操作。其改进过程在于:每当一趟匹配过程岀现字符比较不相等吋，不需冋溯i指针，而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后，继续进行比较。滑动
7、的这一段距离我们将会用到函数next[],KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程屮，对主串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边度入边匹配，而无需回头重读。2.问题分析2.1问题的分析和任务的定义用C/C++编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜索某个子串，若搜索到就返冋子串的位置；若未搜索到，就返冋0。首先要输入个主串和模式串,先根据next()函数求模式串的next值，利用KMP算法进行匹配，再用输出函数输出结果！2.2设计过程本次课程设计利用模式匹配KMP算法实现串
8、的相关操作：分别从键盘上任意输入三组字符串作为主串，在任意数取三组字符串作为模式串，利用《模式匹配KMP算法》依次使三组模式串与三组主串匹配，在使用《模式匹配KMP算法》时会调用到GetnextO函数。2.
