2022年模式匹配KMP算法研究报告.docx

精品学习资源模式匹配的 KMP算法争论同学姓名：黄飞指导老师：罗心摘 要在运算机科学领域，串的模式匹配 <以下简称为串匹配）算法始终都是争论焦点之一；在拼写检查、语言翻译、数据压缩、搜寻引擎、网络入侵检测、运算机病毒特点码匹配以及 DNA序列匹配等应用中，都需要进行串匹配；串匹配就是在主串中查找模式串的一个或全部显现；在本文中主串表示为S=s1s2s3 sn，模式串表示为T=t1t2 tm；串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，闻名的匹配算法有 BF 算法、 KMP算法、 BM算法及一些改进算法；本文主要在精确匹配方面对KMP算法进行了争论并对它做一些改进以及利用改进的KMP来实现多次模式匹配；关键字：模式匹配；主串；模式串； KMP算法Research and Analysis of KMP Pattern MatchingAlgorithmStudent:HuangfeiTeacher:LuoxinAbstract In computer science,String pattern matchingHereinafter referred to as the string matching>algorithmis always the focus of the study.In thespellcheck,languagetranslation,datacompression,searchengine,the network intrusion detection system, a computer virus signature matching DNA欢迎下载精品学习资源sequences and the application in the match,matched to string matching.String matching is in search of a string of pattern or all appear.In this paper, the string is S = s1s2s3. Sn, string pattern for T= t1t2. tm.String matching way can be divided from the accurate matching, fuzzy matching, parallel matching etc., the famous matching algorithms are KMP algorithm, BF algorithm, the algorithm and some BM algorithm.This paperinpreciseKMP algorithmformatchingaspectsarediscussedandsome improvementonitandusingtheimprovedKMP torealizethemultiple pattern matching.Key words : pattern matching, The string； Pattern strings；KMP algorithm1 引言KMP算 法是是对 一般模 式匹配算法 的改进， 由 D.E.Knuth 与 V.R.Pratt 和J.H.Morris 同时发觉的因此人们称它为克努特 - 莫里斯 - 莫拉特操作 <简称为 KMP算法）；对于一般的模式匹配算法：分别利用两个指针i 和 j 指示主串 S 和 T 中的当前正待比较的字符位置；算法的基本思想是：从主串的S 的第 POS个字符开头起和模式的第一个字符比较之，如相等，就连续逐个比较后续字符；否就从主串的下一个字符起再重新和模式的字符比较之；以此类推，直到模式T 中的每个字符依次和主串S 中的一个连续字符序列相等，就称匹配胜利，就函数值为和模式T 中的第一个字符相等的字符在主串 S 中的序号，否就称匹配不胜利，函数值为0. 而对于模式匹配的 KMP算法可以在 On+m>的时间数量级上完成串的模式匹配操作；其改进过程在于: 每当一趟匹配过程显现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配的结果 将模式串向右滑动一段尽可能远的距离后，连续进行比较；滑动的这一段距离我们将会用到函数 next,KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到欢迎下载精品学习资源尾扫描一遍，这对处理从外设输入的巨大文件很有效，可以边度入边匹配，而无需回头重读；2、问题分析2.1 问题的分析和任务的定义用 C/C+编写一个程序实现模式匹配的KMP算法；要求在一个字符串中搜寻某个子串，如搜寻到就返回子串的位置；如未搜寻到，就返回0； 第一要输入个主串和模式串，先依据 next >函数求模式串的next值，利用 KMP算法进行匹配，再用输出函数输出结果！2.2 设计过程本次课程设计利用模式匹配KMP算法实现串的相关操作：分别从键盘上任意输入 三组字符串作为主串，在任意数取三组字符串作为模式串，利用模式匹配KMP算法依次使三组模式串与三组主串匹配，在使用模式匹配KMP算法时会调用到Getnext> 函数；2.3 规律设计对该 kmp 算法，定义的抽象数据类型如下： ADT String数据对象： D=ai|aiCharacterSet,i=1,2,3,n,n 0 数据关系： R1=<ai-1,ai>|ai-1,ai D,i=2, ,n基本操作： StrAssign&T,chars>初始条件： chars 是字符串常量；操作结果：生成一个其值等于 chars 的串 T；StrCopy<S）初始条件：串 S存在；操作结果：如 S为空串，就返回 TRUE，否就返回 FALSE； StrLengthS>欢迎下载精品学习资源初始条件：串 S存在；操作结果：返回 S元素的个数，成为串的长度；IndexS,T,pos>初始条件：串 S和 T 存在， T 是非空串， 1posStrLengthS>.操作结果：如主串 S 中存在和串 T 相同的子串，就返回他在主串S 中的第 pos 个字符之后第一次显现的位置；否就函数值为0；DestoryString&S> 初始条件：串 S存在；操作结果：串 S被销毁；ADT String该算法是对进行操作，对串的储备结构用定长次序储备表示：类似于现性表的次序储备结构，用一组地址连续的储备单元储备串值得字符序列；在串的定长次序储备结构中，依据与定义大小，为每个定义的串安排一个固定长度的储备区，就可用定长数组如下描述；#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1该算法分为五三个模块：第一模块StrLength< ）< 利用该函数求各串的长度）；其次模块input >函数< 利用该函数输入主串和模式串的值）；第三模块get_next >函数< 利用该函数求出模式串的 next函数值）；第四模块 Index_KM<）函数< 利用该函数进行主串和模式串之间的匹配）；第五模块output >函数利用该函数输出匹配结 果）；个模块之间的调用关系如下图所示：图4.1 是对整个函数的流程图；图4.2是对 KMP算法的流程图；图 4.3 是求 next 的函数值的流程图；欢迎下载精品学习资源开头欢迎下载精品学习资源用intput输入串next函 数值欢迎下载精品学习资源欢迎下载精品学习资源StrLength 输出长m度,nget_nextNIndex_KM（P）i=pos-1,j=-1 m=StrLengths; n=StrLengtht;Nj=-1 | si=tjY输出匹配结果调用output 终止欢迎下载精品学习资源i<nYj=0 | si-1=sj-1YNi+; j+;nexti-1=j; j=nextj-1不能匹配i+; j+;j=nextj-1YNj>=ltYi-lt+10欢迎下载精品学习资源图 2.1 模块调用流程图3、解决方案3.1 为主串和模式串赋值分别定义三组字符串作为主串str1,str2,str3,利用 cin 函数依次为为三组字符串欢迎下载精品学习资源赋值，从键盘上任意输入字符分别赋给str1 str2 str3,；以同样的方法模模式串p1,p2,p3 赋值；3.2 求各串的长度StrLength< ）函数求的各串的长度，利用一个while循环语句，为后面的函数做好预备工作；3.3 求模式串的模式值 next函数用模式匹配的 KMP算法当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next 函数值；如何求 next 函数， next 函数值仅取决于模式本身而和主串无关；我们可以从分析next函数的定义动身用递推的方法求得next函数值；由定义知：next1=0设nextj=k，即有： t1 t2 tk-1 = tj-k+1 tj-k+2 tj-1 nextj+1=.可 能 有 两 种 情 况 ： 一 种 情 况 ： 如 tk tj就 表 明 在 模 式 串 中 这 就 是 说nextj+1=k+1，即 nextj=nextj+1其次种情形：如 tktj就说明在模式串中 t1 t2 tk tj-k+1 tj-k+2 tj此时可把求 next 函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有4.6> 式成立，就当 tktj时应将模式向右滑动，使得第nextk个字符和“主串” 中的第 j 个字符相比较；如 nextk=k，且 t k tj ，就说明在主串中第 j+1 个字符之前存在一个最大长度为k的子串，使得 t1 t2 t k =tj-k+1 tj- k +2 tj 此： nextj+1=nextk+1同理如 t k tj ，就将模式连续向右滑动至使第nextk 个字符和 tj对齐， 依此类推，直至 tj和模式中的某个字符匹配胜利或者不存在任何k 1< k <k < <j> 满意 ， 此 时如 t1 tj+1， 就 有： nextj+1=1否就如 t1=tj+1， 就有：nextj+1=0综上所述，求 next 函数值过程的算法如下：void get _nextchar t,int next >/* 求模式 t 的 next 值并寸入 next 数组中 */ int i=1,j=0；next0=0 ；欢迎下载精品学习资源while i<t0> while j=0|ti-1 = =tj-1> +i；+j ；nexti-1=j； ；else j=nextj-1；/get_next3.4 模式匹配 KMP算法的实现KMP算法的思想：主串s，模式 t 期望某趟在 si和 tj匹配失败后，指针i不回溯，模式 t向右“滑动”至某个位置上，使得tk对准 s i连续向右进行；明显，现在问题的关键是串 t “滑动”到哪个位置上？不妨设位置为k，即 si和 tj匹配失败后，指针 i不动，模式 t 向右“滑动”，使tk 和 si对准连续向右进行比较，要满意这一假设，就要有如下关系成立：t1 t2 tk-1 = si-k+1 si-k+2 si- 1 4.1> 式左边是 tk 前面的 k-1 个字符，右边是 si前面的 k-1 个字符；而本趟匹配失败是在 si 和 tj之处，已经得到的部分匹配结果是： t1 t2 tj-1 = si- j+1 si-j+2si-1 <4.2 ）由于k<j ，所以有： tj-k+1 tj-k+2 tj-1= si-k+1 si-k+2si-1 4.3> 式左边是 tj前面的 k-1个字符，右边是 si前面的 k-1个字符，通过 4.1> 和4.3> 得到关系： t1 t2 tk-1 = tj-k+1 tj-k+2 tj-1 4.4> 结论：某趟在 si和 tj匹配失败后，假如模式串中有满意关系4> 的子串存在，即：模式中的前k-1 个字符与模式中 tj字符前面的 k-1 个字符相等时，模式 t 就可以向右“滑动”至使 tk 和 si 对准，连续向右进行比较即可；在求得模式的 next 函数之后，匹配可如下进行：假设以指针i 和 j 分别指示主串和模式中的比较字符，令 i 的初值为 pos，j 的初值为 1；如在匹配过程中 si tj ，就 i 和j分别增，如 si tj匹配失败后，就 i不变， j退到 nextj位置再比较，如相等，就指针各自增，否就 j 再退到下一个 next 值的位置，依此类推；直至以下两种情形：一种是 j 退到某个 next 值时字符比较相等，就i 和 j 分别增连续进行匹配；另一种是 j 退到值为零 <即模式的第一个字符失配），就此时i 和 j 也要分别增，说明从主串的下一个字符起和模式重新开头匹配；KMP算法如下：int StrIndex_KMPchar *s,char *t,int pos>/* 从串 s 的第 pos 个字符开头找首次与串t 相等的子串 */欢迎下载精品学习资源 int i=pos,j=-1,slen,tlen；while i<=s0 && j<=t0 > /*都没遇到终止符 */ if j=-1|s=tj> i+； j+ ； else j=nextj-1； /* 回溯*/if j>t0> return i-t0+1；/* 匹配胜利，返回储备位置 */ else return 04 程序调试与测试4.1 如匹配胜利：调试结果如下图所示图 4.1匹配胜利4.2 如匹配不胜利：调试结果如下所示欢迎下载精品学习资源图 4.2 匹配不胜利4.3 结果分析利用该程序求模式串是否可以在主串中找到，先利用next >函数求的模式串的next函数值，利用 for循环语句分别输出next函数值： <0，1，2，3，4）； <0， 1， 2， 3） <0，1， 1，2，2， 3，1，2），再用 KMP算法进行查找，如查找胜利就输出模式串在主串中的位置 :9 ,8, 9.如没有找到就返回 0；该调试结果与程序相对应；对于模式匹配 KMP算法时间复杂度为 O<n+m）；对于 next >函数的时间复杂度为 O<m） 其中 n 表示主串的长度， m表示子串的长度 ；5 终止语在这次课程设计中，我做的一个简洁的模式匹配的kmp 的算法，该算法是对一般算法的改进， kmp算法仅当模式与主串之间存在部分匹配时才比一般模式匹配算法快；其次该算法的最大特点是，指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头到尾扫描一遍，这时处理从外设输入的巨大文件有很大的成效，可以边输入边匹配，而无需回头读；刚开头，对求子串的next值时，我仅对一串字符进行实例说明，经过自己和组员的争论，我们共同争论才开头懂得了该算法的应用，；让我们体验到了“过程是完善的”；正如一句话所说的，“我们可以错过一路风景，但不能错过终点站”我将之欢迎下载精品学习资源改为“我可以不在乎结果，但我们永久记得过程最美”；一个好的程序=好结构 +好结构，这次课设真让我体验到这句话；当然，通过这次课程设计，我也发觉了自身的许多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的进展；在以后的工作中，我会补偿自己在设计方面的不足；在工作中，学会合作；其次，感谢老师， 学校给我供应的这次机会！参考文献1 严蔚敏 吴伟民数据结构 <c 语言版）北京 . 清华出版社 .20212 王宏生 宋继红数据结构北京 . 国防工业出版社 .20063 彭波数据结构教程北京 . 清华出版社 .20044 谭浩强 c+程序设计北京 . 清华高校出版社 .20215 陈杰运算机专业课程设计中的需求分析J 集美高校学报 .20216 高一凡数据结构算法实现及解读 M 西安. 西安电子科技高校出版社 . 20027 黄国瑜 叶乃箐数据结构 <c 语言版）北京 . 清华高校出版社 .2001附录：欢迎下载精品学习资源程序清单# include"iostream.h" # include "string"# include"stdlib.h" #define MaxStrLen 200 chars1MaxStrLen,s2MaxStrLen,s3MaxStrLen,p120,p220,p320；int next20；int StrLengthchar* s>；void input>；int Index_KMPchar* s,char* t,int pos,int next>；void get_nextchar* s,int next>；void output>；int StrLengthchar* s>int i,len；i=0 ；len=0 ；whilesi.='0'> len+=1；i+ ；return len；void input> /利用该函数为串赋值；cout<<"please input the main string of S1:n"；cin>>s1 ；cout<<"please input the main string of S2:n"；cin>>s2 ；cout<<"please input the main string of S3:n"；cin>>s3 ；cout<<"please input the sub string of p1:n"；cin>>p1 ；欢迎下载精品学习资源cout<<"please input the sub string of p2:n"；cin>>p2 ；cout<<"please input the sub string of p3:n"；cin>>p3 ；int Index_KMPchar* s,char* t,int pos,int next>/利用模式 t 的 next 函数求主串 s 中的第 pos 个字符后的位置；/ 串 s 和 t 采纳定长次序储备 , 且 t 非空,1<=pos<=strlents>-strlentt>+1. int i,j,ls,lt；i=pos-1,j=-1；/ 设置初值ls=StrLengths>； /求主串 s 的长度lt=StrLengtht>；/ 求模式串 t 的长度whilei<ls && j<lt> ifj=-1 | si=tj> /连续比较后继字符i+； j+ ；else j=nextj-1； /模式串向右移if j>=lt> return i-lt+1；/ 匹配胜利else return 0；/ 匹配不胜利void get_nextchar* s,int next> /求模式串的 next 函数值并 存入数组 next, 为后面进行模式匹配做预备int i,j；欢迎下载精品学习资源i=1 ； j=0 ；/ 设置初值next0=0；while i<StrLengths>>if j=0 | si-1=sj-1>/如 j=0 或 si-1=sj-1,令 nexti=j+1.i+； j+ ；nexti-1=j；elsej=nextj-1；/ 如 j.=0或 si-1.=sj-1,令 j=nextj-1cout<<"next="<<'t'；for i=0；i<StrLengths>；i+> cout<<nexti<<", "；cout<<endl ；void output> cout<<"子串 p1 在主串 s1 的"<<Index_KMPs1,p1,0,next><<"相匹配"<<'n'；cout<<"子串 p2 在主串 s2 的"<<Index_KMPs2,p2,0,next><<"相匹配"<<'n'；cout<<"子串 p3 在主串 s3 的"<<Index_KMPs3,p3,0,next><<"相匹配"<<'n'；void main>input> ；get_nextp1,next>；get_nextp2,next>；get_nextp3,next>；欢迎下载精品学习资源cout<<endl ；output> ；欢迎下载