KMP模式匹配算法.docx

KMP模式匹配算法.docx

ID:55209711

大小:15.08 KB

页数:4页

时间:2020-05-03

KMP模式匹配算法.docx_第1页
KMP模式匹配算法.docx_第2页
KMP模式匹配算法.docx_第3页
KMP模式匹配算法.docx_第4页
资源描述:

《KMP模式匹配算法.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、1.KMP算法是一种线性时间复杂度的字符串匹配算法,它是对BF算法(Brute-Force,最基本的字符串匹配算法)的改进。对于给定的原始字符串string和模式字符串p,需要从字符串s中找出p(首次)出现的位置索引:BF算法的时间复杂度为O(strlen(s)*strlen(p)),空间复杂度为O(1);KMP算法的时间复杂度为O(strlen(s)+strlen(p)),空间复杂度为O(strlen(p));2.两种算法的主要区别是失配时的处理:假设串s匹配到i位置,串p匹配到j位置:BF算法中,如果当前字符匹配成功,即

2、s[i+j]==p[j],则令j++,继续匹配下一个字符;如果匹配失败,即s[i+j]!=p[j],则让i++并且j=0,即每次失配时,原串匹配位置向右移动一位(从i+j回溯到i+1),而j重置为0。而KMP算法则是在发生失配时,根据模式中字符和失配在模式中出现的位置,来确定继续进行搜索(j)的位置,而i的位置不会向后回溯。3.例如:假定p=’abcabcacab’,令字符串s=s0s1…sm-1,且假设现在要判断是否存在从si开始的匹配。a.如果si≠a,那么显然可以进行si+1与a的比较;b.类似地,如果si=a且si+

3、1≠b,那么进行si+1与a的比较;c.如果sisi+1=ab且si+2≠c,则出现如下情况:s=-ab???…?p=’abcabcacab’符号?表示不知道s中此处字符是什么,在s中第一个?代表si+2且si+2≠c,因此,搜索的下一步应该是对p的首字符和si+2进行比较。这里无需比较p的首字符和si+1,因为已经知道si+1与p的第二个字符相同为b,即si+1≠a;a.以此类推,假定出现了p前4个字母的匹配,然后失配,即si+4≠b。则出现如下情况:s=-abca???…?p=’abcabcacab’通过观察可以看到,匹

4、配搜索可以继续把si+4与第二个字符b进行比较。这是在把模式p向右滑动时,发生部分匹配的第一处。因此,通过模式中的字符和失配在模式中出现的位置,就可以确定在模式中继续进行匹配搜索的位置,而不必在s中进行回溯。1.为了形式化说明,定义一个模式失配函数:令p=p0p1…pn-1是一个模式,则其失配函数f定义为:fj=i为满足i

5、根据失配函数的定义,得到如下模式匹配规则:如果出现了形如si-j…si-1=p0p1…pj-1且si≠pj的部分匹配,,若j≠0,则下一趟模式匹配时,从失配字符si和模式串字符pfj-1+1处重新开始比较;若j=0,则继续比较si+1和p0。按上述匹配规则实现的匹配函数为:intstr_pmatch(char*s,char*p,char*failure){if(NULL==s

6、

7、NULL==p

8、

9、NULL==failure){return-1;}intlens=strlen(s);intlenp=strlen(p);inti

10、=0,j=0;while(i

11、配函数,需要利用失配函数的令一种表达形式:fj=-1,如果j=0fmj-1+1,如果m满足等式pfkj-1+1=pj的最小整数k-1,如果没有满足上式的k值注意:f1j=fj,fmj=ffm-1j。(这个表达形式如何证明??)和以上定义对应的失配函数计算方法如下:voidstr_fail(char*pat,char*failure){intn=strlen(pat);failure[0]=-1;for(intj=1;j=0

12、){i=failure[i];}if(pat[j]==pat[i+1])failure[j]=i+1;elsefailure[j]=-1;}}

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。