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

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(kk 满足下列关系式：(kj), p(1) p(2) p(3).p(k-1) = s(i-k+1)s(i-k+2)s(i-1) 即： 主串： s(1)s(i-k +1) s(i-k +2) s(i-1) s(i) . | (相配) | | ?(有待比较) 匹配串： p(1) p(2) . p(k-1) p(k) 现在我们把前面总结的关系综合一下 有： s(1)s(i-j +1) s(i-k +1) s(i-k +2) s(i-1) s(i) | (相配) | | | (失配) p(1) p(j-k+1) p(j-k+2) . p(j-1) p(j) | (相配) | | ?(有待比较) 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)。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码) K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。 课本83页不是有个例子吗？就是 图4.6 你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。 在理解上面代码的基础上，建议自己寻找一些KMP算法的练习，也可以自己写两个较为简单的字符串进行人脑模拟这种方法的练习，以加深对算法的理解。 KMP算法的优化KMP算法是可以被进一步优化的。 我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i0123456789p(i)abcdaabcabnexti-1000011231但是，如果此时发现p(i) = p(k)，那么应当将相应的nexti的值更改为nextk的值。经过优化后可以得到下面的表格： 下标i0123456789p(i)abcdaabcabnexti-1000112312优化的nexti-1000-110030附：（以下为本人已调试通过的进行两种模式匹配的算法，直接复制即可运行。）#include#include#define MAXSIZE 100int Index_BF ( char S , char T , int pos );int KMP(char *Text,char* Pattern,int pos);void main()int k,pos,n;char s11MAXSIZE;char s22MAXSIZE;doprintf(*主菜单*);printf(n1.输入待匹配的两个字符串);printf(n2.模式匹配的朴素算法进行匹配);printf(n3.模式匹配的KMP算法进行匹配);printf(n4.结束程序);printf(n请输入您的选择(以输入10表结束:);scanf(%d,&k);switch(k)case 1:printf(please input the MAINLY string :);scanf(%s,s11);printf(please input the MODE string :);scanf(%s,s22);printf(please enter the position you want to start:);scanf(%d,&pos);break; case 2:n=Index_BF(s11,s22,pos);if(n!=-1) printf(normal mode:have found ,at the position:%d.,n);else printf(normal mode:have NOT found!);break; case 3:n=KMP(s11,s22,pos);if(n!=-1) printf(KMP:have found ,at the position:%d.,n);else printf(KMP:have NOT found!);break; case 4:printf(感谢使用，GOODBYE!n);break;printf(n*nnn);while(k!=4);int Index_BF ( char S , char T , int pos ) /模式匹配的朴素算法 int i=pos,j=0;while (Si+j!=0&Tj!=0) if(Si+j=Tj) j +; / 继续比较后一字符else i+; j=0; if ( Tj = 0) return i; / 匹配成功 返回下标else return -1; void getNext(const char* pattern,int next) /用于求nextj的值 next0=-1; int k=-1,j=0; while(patternj != 0) if(k!= -1 & patternk!= patternj ) k=nextk; +j;+k; if(patternk= patternj) nextj=nextk; else nextj=k; int KMP(char *Text,char* Pattern,int pos) /模式匹配的KMP算法 if( !Text|!Pattern| Pattern0=0 | Text0=0 ) return -1;/空指针或空串，返回-1。 int len=0; char * c=Pattern; while(*c+!=0) +len;int *next=new intlen+1; getNext(Pattern,next); int index=0,i=pos-1,j=0; while(Texti!=0 & Patternj!=0 ) if(Texti= Patternj) +i;/ 继续比较后继字符