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

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

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用模式匹配的 KMP算法争论同学姓名：黄飞指导老师：罗心摘要在运算机科学领域,串的模式匹配algorithmis always the focus of the study.In the spell check, language translation, data compression, search engine, the network intrusion detection system, a computer virus signature matching DNA 名师归纳总结 - - - - - - -第

2、 1 页,共 14 页精选学习资料 - - - - - - - - - sequences and the application 个人资料整理仅限学习使用string in the match,matched to 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

3、 the accurate matching, fuzzy matching, parallel matching etc., the famous matching algorithms are KMP algorithm, BF algorithm, the algorithm and some BM algorithm.This paper in precise KMP algorithm for matching aspects are discussed and some improvement on it and using the improved KMP to realize

4、the multiple pattern matching.Key words : pattern matching, The string； Pattern strings；KMP algorithm1 引言KMP算 法 是 是对 一 般模 式 匹 配 算法 的 改进, 由 D.E.Knuth与 V.R.Pratt和J.H.Morris 同时发觉的因此人们称它为克努特- 莫里斯 - 莫拉特操作 的时间数量级上完成串的模式匹配操作；其改进过程在于 : 每当一趟匹配过程显现字符比较不相等时,不需回溯 i 指针,而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后,连续进行比较；滑

5、动的这一段距离我们将会用到函数 next,KMP算法的最大特点是指示主串的指针不须回溯,整个匹配过程中,对主串仅需从头到名师归纳总结 - - - - - - -第 2 页,共 14 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用尾扫描一遍,这对处理从外设输入的巨大文件很有效,可以边度入边匹配,而无需回头重读；2、问题分析2.1 问题的分析和任务的定义用 C/C+编写一个程序实现模式匹配的KMP算法；要求在一个字符串中搜寻某个子串,如搜寻到就返回子串的位置；如未搜寻到,就返回 0； 第一要输入个主串和模式串,先依据 next 函数求模式串的 next 值,利用 K

6、MP 算法进行匹配,再用输出函数输出结果！2.2 设计过程本次课程设计利用模式匹配KMP算法实现串的相关操作：分别从键盘上任意输入三组字符串作为主串,在任意数取三组字符串作为模式串,利用模式匹配 KMP算 法依次使三组模式串与三组主串匹配,在使用模式匹配 KMP算法时会调用到 Getnext 函数；2.3 规律设计对该 kmp 算法,定义的抽象数据类型如下：ADT String 数据对象： D=ai|aiCharacterSet,i=1,2,3, ,n,n 0 数据关系： R1=|ai-1,aiD,i=2, ,n 基本操作： StrAssign&T,chars 初始条件： chars 是字符串

7、常量；操作结果：生成一个其值等于 chars 的串 T； StrCopy 名师归纳总结 - - - - - - -第 3 页,共 14 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用初始条件：串 S存在；操作结果：返回 S元素的个数,成为串的长度； IndexS,T,pos 初始条件：串 S和 T 存在, T 是非空串, 1posStrLengthS. 操作结果：如主串 S 中存在和串 T 相同的子串,就返回他在主串 S 中的第 pos 个字符 0；之后第一次显现的位置；否就函数值为 DestoryString&S 初始条件：串 S存在；操作结果：串 S被销毁；

8、ADT String 该算法是对进行操作,对串的储备结构用定长次序储备表示：类似于现性表的顺 序储备结构,用一组地址连续的储备单元储备串值得字符序列；在串的定长次序储备结构中,依据与定义大小,为每个定义的串安排一个固定长度的储备区,就可用定长 数组如下描述； #define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1 该算法分为五三个模块：第一模块StrLength ）函数 函数 利用该函数求出模式串的next 函数值）；第四模块 Index_KM）函数 函数利用该函数输出匹配结果）；个模块之间的调用关系如下图所示：图 4.1

9、是对整个函数的流程图；图 4.2 是对 KMP算法的流程图；图4.3 是求 next 的函数值的流程图；名师归纳总结 - - - - - - -第 4 页,共 14 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用开头用intput 输入串next 函数值输出匹配结果StrLength Index_KMP（）输出长度 m,ni=pos-1,j=-1调用output m=StrLengths; n=StrLengtht;get_nextj=-1 | si=tj N终止Yi=ltNi+; j+;nexti-1=j;Yj=nextj-1不能匹配i-lt+10图 2.1

10、模块调用流程图3、解决方案3.1 为主串和模式串赋值名师归纳总结 分别定义三组字符串作为主串str1,str2,str3,利用 cin 函数依次为为三组字符串第 5 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - 赋值,从键盘上任意输入字符分别赋给个人资料整理仅限学习使用str1 str2 str3,；以同样的方法模模式串p1,p2,p3 赋值；3.2 求各串的长度StrLength 式成立,就当 tk tj 时应将模式向右滑动,使得第 nextk 个字符和“ 主串”中的第 j 个字符相比较；如 nextk=k ,且 t k tj ,就说明在主串中第

11、 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 满 足 , 此 时 如 t1 tj+1 ,就 有 ： nextj+1=1 否 就 如 t1=tj+1 , 就 有 ：nextj+1=0 综上所述,求 next 函数值过程的算法如下：void get _nextchar t,int next /* 求模式 t 的 next 值并寸入

12、next 数组中 */ int i=1,j=0；next0=0 ；名师归纳总结 - - - - - - -第 6 页,共 14 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用while i while j=0|ti-1 = =tj-1 +i；+j ；nexti-1=j； ；else j=nextj-1； /get_next 3.4 模式匹配 KMP算法的实现KMP算法的思想：主串 s,模式 t 期望某趟在 si 和 tj 匹配失败后,指针 i 不回溯,模式 t 向右“ 滑动” 至某个位置上,使得 tk 对准 s i 连续向右进行；明显,现在问题的关键是串 t “

13、 滑动” 到哪个位置上？不妨设位置为 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+2 si-1 4.2 ）由于 k 式左边是 tj 前面的 k-1 个字符,右边是 si 前面的 k-1 个字符,通过 4.1 和4.3 得到

14、关系： 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 位置再比较,如

15、相等,就指针各自增,否就j 再退到下一个 next 值的位置,依此类推；直至以下两种情形：一种是 j 退到某个 next 值时字符比较相等,就 i 和 j 分别增连续进行匹配；另一种是 j 退到值为零 名师归纳总结 /* 从串 s 的第 pos 个字符开头找首次与串t 相等的子串 */ 第 7 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 int i=pos,j=-1,slen,tlen；while i=s0 & j /* 都没遇到终止符 */ if j=-1|s=tj i+； j+ ； else j=nextj-1；

16、/* 回溯*/ if jt0 return i-t0+1 else return 0 ；/* 匹配胜利,返回储备位置 */ 4 程序调试与测试4.1 如匹配胜利：调试结果如下图所示图 4.1 匹配胜利4.2 如匹配不胜利：调试结果如下所示名师归纳总结 - - - - - - -第 8 页,共 14 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用图 4.2 匹配不胜利4.3 结果分析利用该程序求模式串是否可以在主串中找到,先利用next 函数求的模式串的next 函数值,利用for 循环语句分别输出next 函数值： 0,1,2,3,4）； 0,1, 2,3）0,

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

18、无需回头读；刚开头,对求子串的 next 值时,我仅对一串字符进行实例说明,经过自己和组员的 争论,我们共同争论才开头懂得了该算法的应用,；让我们体验到了“ 过程是完善名师归纳总结 的” ；正如一句话所说的,“ 我们可以错过一路风景,但不能错过终点站” 我将之第 9 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用改为“ 我可以不在乎结果,但我们永久记得过程最美” ；一个好的程序 =好结构 +好结 构,这次课设真让我体验到这句话；当然,通过这次课程设计,我也发觉了自身的许多不足之处,在以后的学习中,我会不断的完善自我,不断进

19、取,能使自己在编程这方面有一个大的进展；在以后的 工作中,我会补偿自己在设计方面的不足；在工作中,学会合作；其次,感谢老师,学校给我供应的这次机会！参考文献1 严蔚敏 吴伟民数据结构 c 语言版）北京 . 清华出版社 .2022 2 王宏生 宋继红数据结构北京 . 国防工业出版社 .2006 3 彭波数据结构教程北京 . 清华出版社 .2004 4 谭浩强 c+程序设计北京 . 清华高校出版社 .2022 5 陈杰运算机专业课程设计中的需求分析J 集美高校学报 .2022 6 高一凡数据结构算法实现及解读 M 西安 . 西安电子科技高校出版社 . 2002 7 黄国瑜 叶乃箐数据结构 ；voi

20、d 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 / 利用该函数为串赋值；couts1 ；couts2 ；couts3 ；coutp1 ；名师归纳总结 - - - - - - -第 11 页,共 14 页精选学习资料 - - - - - - - - - coutp2 ；coutp

21、3 ； 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,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=l

22、t return i-lt+1；/ 匹配胜利else return 0；/ 匹配不胜利 void get_nextchar* s,int next 名师归纳总结 /求模式串的 next 函数值并存入数组 next, 为后面进行模式匹配做预备第 12 页,共 14 页int i,j；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用i=1 ； j=0 ；/ 设置初值 next0=0 ；while i if j=0 | si-1=sj-1/如 j=0 或 si-1=sj-1,令 nexti=j+1. i+； j+ ； nexti-1=j； els

23、e j=nextj-1；/ 如 j.=0或 si-1.=sj-1,令 j=nextj-1 coutnext=t；for i=0；i；i+ coutnexti, ；cout cout子串 p1 在主串 s1 的相匹配 n； cout子串 p2 在主串 s2 的相匹配 n； cout子串 p3 在主串 s3 的相匹配 input ；名师归纳总结 get_nextp1,next；第 13 页,共 14 页get_nextp2,next；get_nextp3,next；- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用cout ； 名师归纳总结 - - - - - - -第 14 页,共 14 页