KMP算法和朴素算法模式匹配

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

1、KMP算法和朴素算法(后面赋有能直接运行的C语言代码)　　现在讨论一般情况。　　假设　　主串：s:‘s(1)s(2)s(3)……s(n)’;　　模式串：p:‘p(1)p(2)p(3)…..p(m)’　　把课本上的这一段看完后，继续　　现在我们假设主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k

2、

3、(相配)

4、

5、≠(失配)　　匹配串：p(1)...........p(j-1)p(j)　

6、　由此，我们得到关系式：　　‘p(1)p(2)p(3)…..p(j-1)’=’s(i-j+1)……s(i-1)’　　由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在k’>k满足下列关系式：(k

7、

8、(相配)

9、

10、

11、

12、?(有待比较)　　匹配串：p(1)p(2)…….

13、....p(k-1)p(k)　　现在我们把前面总结的关系综合一下　　有：　　s(1)…s(i-j+1)…s(i-k+1)s(i-k+2)……s(i-1)s(i)……　　

14、

15、(相配)

16、

17、

18、

19、

20、

21、≠(失配)　　p(1)……p(j-k+1)p(j-k+2)…......p(j-1)p(j)　　

22、

23、(相配)

24、

25、

26、

27、?(有待比较)　　p(1)p(2)……......p(k-1)p(k)　　由上，我们得到关系：　　'p(1)p(2)p(3)…..p(k-1)’='p(j-k+1)p(j-k+2)……p(j-1)’　　接下来看“反之，若模式串中存在满足式(4-4

28、)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)　　K是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。　　课本83页不是有个例子吗？就是图4.6　　你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。　　在理解上面代码的基础上，建议自己寻找一些KMP算法的练习，也可以自己写两个较为简单的字符串进行人脑模拟这种方法的练习，以加深对算法的理解。KMP算法的优化　　KMP算法是可以被进一步优化

29、的。　　我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示：　　下标i0123456789p(i)abcdaabcabnext[i]-1000011231但是，如果此时发现p(i)==p(k)，那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格：　　下标i0123456789p(i)abcdaabcabnext[i]-1000112312优化的next[i]-1000-110030附：（以下为本人已调试通过的进行两种模式匹配的算法，直接复制即可运

30、行。）#include#include#defineMAXSIZE100intIndex_BF(charS[],charT[],intpos);intKMP(char*Text,char*Pattern,intpos);voidmain(){intk,pos,n;chars11[MAXSIZE];chars22[MAXSIZE];do{printf("*********************主菜单*********************");printf("1.输入待匹配的两个字符串");printf(

31、"2.模式匹配的朴素算法进行匹配");printf("3.模式匹配的KMP算法进行匹配");printf("4.结束程序");printf("请输入您的选择(以输入10表结束:)");scanf("%d",&k);switch(k){case1:{printf("pleaseinputtheMAINLYstring:");scanf("%s",s11);printf("pleaseinputtheMODEstring:");scanf("%s",s22);printf("pleaseenterthepositionyouwantto

32、start:");scanf("%d",&pos);break;}case2:{n=Index_BF(s11,s22,po