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

《2022年模式匹配KMP算法研究报告.docx》由会员分享，可在线阅读，更多相关《2022年模式匹配KMP算法研究报告.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源模式匹配的 KMP算法争论同学姓名：黄飞指导老师：罗心摘 要在运算机科学领域，串的模式匹配 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

2、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 K

3、MP 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算 法是是对 一般模 式

4、匹配算法 的改进， 由 D.E.Knuth 与 V.R.Pratt 和J.H.Morris 同时发觉的因此人们称它为克努特 - 莫里斯 - 莫拉特操作 的时间数量级上完成串的模式匹配操作；其改进过程在于: 每当一趟匹配过程显现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配的结果 将模式串向右滑动一段尽可能远的距离后，连续进行比较；滑动的这一段距离我们将会用到函数 next,KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到欢迎下载精品学习资源尾扫描一遍，这对处理从外设输入的巨大文件很有效，可以边度入边匹配，而无需回头重读；2、问题分析2.1 问题的分析

5、和任务的定义用 C/C+编写一个程序实现模式匹配的KMP算法；要求在一个字符串中搜寻某个子串，如搜寻到就返回子串的位置；如未搜寻到，就返回0； 第一要输入个主串和模式串，先依据 next 函数求模式串的next值，利用 KMP算法进行匹配，再用输出函数输出结果！2.2 设计过程本次课程设计利用模式匹配KMP算法实现串的相关操作：分别从键盘上任意输入 三组字符串作为主串，在任意数取三组字符串作为模式串，利用模式匹配KMP算法依次使三组模式串与三组主串匹配，在使用模式匹配KMP算法时会调用到Getnext 函数；2.3 规律设计对该 kmp 算法，定义的抽象数据类型如下： ADT String数据

6、对象： D=ai|aiCharacterSet,i=1,2,3,n,n 0 数据关系： R1=|ai-1,ai D,i=2, ,n基本操作： StrAssign&T,chars初始条件： chars 是字符串常量；操作结果：生成一个其值等于 chars 的串 T；StrCopy欢迎下载精品学习资源初始条件：串 S存在；操作结果：返回 S元素的个数，成为串的长度；IndexS,T,pos初始条件：串 S和 T 存在， T 是非空串， 1posStrLengthS.操作结果：如主串 S 中存在和串 T 相同的子串，就返回他在主串S 中的第 pos 个字符之后第一次显现的位置；否就函数值为0；Des

7、toryString&S 初始条件：串 S存在；操作结果：串 S被销毁；ADT String该算法是对进行操作，对串的储备结构用定长次序储备表示：类似于现性表的次序储备结构，用一组地址连续的储备单元储备串值得字符序列；在串的定长次序储备结构中，依据与定义大小，为每个定义的串安排一个固定长度的储备区，就可用定长数组如下描述；#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1该算法分为五三个模块：第一模块StrLength ）函数函数 利用该函数求出模式串的 next函数值）；第四模块 Index_KM）函数函数利用该函数输出

8、匹配结 果）；个模块之间的调用关系如下图所示：图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=ltYi-lt+10欢迎下载精品学习资源图 2.1 模块调用流程图3、解决方案3.

9、1 为主串和模式串赋值分别定义三组字符串作为主串str1,str2,str3,利用 cin 函数依次为为三组字符串欢迎下载精品学习资源赋值，从键盘上任意输入字符分别赋给str1 str2 str3,；以同样的方法模模式串p1,p2,p3 赋值；3.2 求各串的长度StrLength 式成立，就当 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同理如

10、t k tj ，就将模式连续向右滑动至使第nextk 个字符和 tj对齐， 依此类推，直至 tj和模式中的某个字符匹配胜利或者不存在任何k 1 k k 满意 ， 此 时如 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 while j=0|ti-1 = =tj-1 +i；+j ；nexti-1=j；

11、；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 个字符；而本

12、趟匹配失败是在 si 和 tj之处，已经得到的部分匹配结果是： t1 t2 tj-1 = si- j+1 si-j+2si-1 4.2 ）由于k 式左边是 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 函数之后，匹配可如下进

13、行：假设以指针i 和 j 分别指示主串和模式中的比较字符，令 i 的初值为 pos，j 的初值为 1；如在匹配过程中 si tj ，就 i 和j分别增，如 si tj匹配失败后，就 i不变， j退到 nextj位置再比较，如相等，就指针各自增，否就 j 再退到下一个 next 值的位置，依此类推；直至以下两种情形：一种是 j 退到某个 next 值时字符比较相等，就i 和 j 分别增连续进行匹配；另一种是 j 退到值为零 /* 从串 s 的第 pos 个字符开头找首次与串t 相等的子串 */欢迎下载精品学习资源 int i=pos,j=-1,slen,tlen；while i=s0 & j /

14、*都没遇到终止符 */ if j=-1|s=tj i+； j+ ； else j=nextj-1； /* 回溯*/if jt0 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

15、，2），再用 KMP算法进行查找，如查找胜利就输出模式串在主串中的位置 :9 ,8, 9.如没有找到就返回 0；该调试结果与程序相对应；对于模式匹配 KMP算法时间复杂度为 O函数的时间复杂度为 Om） 其中 n 表示主串的长度， m表示子串的长度 ；5 终止语在这次课程设计中，我做的一个简洁的模式匹配的kmp 的算法，该算法是对一般算法的改进， kmp算法仅当模式与主串之间存在部分匹配时才比一般模式匹配算法快；其次该算法的最大特点是，指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头到尾扫描一遍，这时处理从外设输入的巨大文件有很大的成效，可以边输入边匹配，而无需回头读；刚开头，对求子串

16、的next值时，我仅对一串字符进行实例说明，经过自己和组员的争论，我们共同争论才开头懂得了该算法的应用，；让我们体验到了“过程是完善的”；正如一句话所说的，“我们可以错过一路风景，但不能错过终点站”我将之欢迎下载精品学习资源改为“我可以不在乎结果，但我们永久记得过程最美”；一个好的程序=好结构 +好结构，这次课设真让我体验到这句话；当然，通过这次课程设计，我也发觉了自身的许多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的进展；在以后的工作中，我会补偿自己在设计方面的不足；在工作中，学会合作；其次，感谢老师， 学校给我供应的这次机会！参考文献1 严蔚敏 吴

17、伟民数据结构 c 语言版）北京 . 清华出版社 .20212 王宏生 宋继红数据结构北京 . 国防工业出版社 .20063 彭波数据结构教程北京 . 清华出版社 .20044 谭浩强 c+程序设计北京 . 清华高校出版社 .20215 陈杰运算机专业课程设计中的需求分析J 集美高校学报 .20216 高一凡数据结构算法实现及解读 M 西安. 西安电子科技高校出版社 . 20027 黄国瑜 叶乃箐数据结构 ；void input；int Index_KMPchar* s,char* t,int pos,int next；void get_nextchar* s,int next；void out

18、put；int StrLengthchar* sint i,len；i=0 ；len=0 ；whilesi.=0 len+=1；i+ ；return len；void input /利用该函数为串赋值；couts1 ；couts2 ；couts3 ；coutp1 ；欢迎下载精品学习资源coutp2 ；coutp3 ；int Index_KMPchar* s,char* t,int pos,int next/利用模式 t 的 next 函数求主串 s 中的第 pos 个字符后的位置；/ 串 s 和 t 采纳定长次序储备 , 且 t 非空,1=pos-strlentt+1. int i,j,ls,

19、lt；i=pos-1,j=-1；/ 设置初值ls=StrLengths； /求主串 s 的长度lt=StrLengtht；/ 求模式串 t 的长度whileils & j 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

20、=0；while iif 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-1coutnext=t；for i=0；i；i+ coutnexti, ；cout cout子串 p1 在主串 s1 的相匹配n；cout子串 p2 在主串 s2 的相匹配n；cout子串 p3 在主串 s3 的相匹配input ；get_nextp1,next；get_nextp2,next；get_nextp3,next；欢迎下载精品学习资源cout ；欢迎下载