完整串的模式匹配程序.docx

串的模式匹配字符串模式匹配算法，通俗点说，就是一种在一个字符串中定位另一个串的高效算法。KMP(Knuth-Morris-Pratt)算法是一种基于前缀搜索的方法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法在搜索阶段的最坏时间复杂度和平均时间复杂度都是O(n),在预处理阶段的时间复杂度是O(m)，所以它的时间复杂度为O(m+n)。 一.简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos )/* 若串 S 中从第pos(S 的下标0pos S0 != S1,S1 != S2,所以S1 != T0,S2 != T0. 还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况。假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0 间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn呢？（本文中next值、模式函数值、模式值是一个意思。） 三. 怎么求串的模式值nextn定义：（1）next0= -1 意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad” 则 next6=-1，因T3=T6（3）nextj=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj != Tk （1kj）。 即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 ,且Tj != Tk.（1kj）;(4) nextj=0 意义：除（1）（2）（3）的其他情况。 举例：01）求T=“abcac”的模式函数的值。 next0= -1 根据（1） next1=0 根据 (4) 因（3）有1=kj;不能说，j=1,Tj-1=T0 next2=0 根据 (4) 因（3）有1=k0 但kn, 表示,Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？4. 其他值，不可能。 四. 求串T的模式值nextn的函数下面是这个函数: void get_nextval(const char *T, int next) / 求模式串T的next函数值并存入数组 next。 int j = 0, k = -1; next0 = -1; while ( Tj != 0 ) if (k = -1 | Tj = Tk) +j; +k; if (Tj!=Tk) nextj = k; else nextj = nextk; / if else k = nextk; / while /显示部分 / for(int i=0;ij;i+) / / coutnexti; / /coutendl;/ get_nextval另一种写法，也差不多。void getNext(const char* pattern,int next) 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; /显示部分 / for(int i=0;ij;i+) / / coutnexti; / /coutendl;下面是KMP模式匹配程序，加入上面的函数#include #include #includevoid get_nextval(const char *T, int next) / 求模式串T的next函数值并存入数组 next。 int j = 0, k = -1; next0 = -1; while ( Tj/*+1*/ != 0 ) if (k = -1 | Tj = Tk) +j; +k; if (Tj!=Tk) nextj = k; else nextj = nextk; / if else k = nextk; / while /这里是显示部分 / for(int i=0;ij;i+) / / coutnexti; / /coutendl;/ get_nextvalvoid KMP(const char *Text,const char* Pattern,int pos) /const 表示函数内部不会改变这个参数的值。 if( !Text|!Pattern| Pattern0=0 | Text0=0 ) cout错误;/空指针或空串，错误。 int len=0; const char * c=Pattern; while(*c+!=0)/移动指针比移动下标快。 +len;/字符串长度。 int *next=new intlen+1; get_nextval(Pattern,next);/求Pattern的next函数值 int i=pos,j=0; while(Texti!=0 & Patternj!=0 ) if(Texti= Patternj) +i;/ 继续比较后继字符 +j; else if(nextj!=-1) j=nextj;/ 模式串向右移动 else j=0; +i; /while delete next; if(Patternj=0) cout匹配成功endl;/ 匹配成功 else cout匹配不成功endl; int main()system(color e4); char tex