模式匹配KMP算法及疑难点解析

模式匹配：KMP算法及疑难点解析以下代码为模式匹配的暴力算法、MP和KMP算法（MP与KMP的不同之处在于next[]数组的不同）源代码:#includestdio.h#includestring.h#includemalloc.hintViolentMatch(char*s,char*p);intKMPMatch(char*s,char*p);voidmain(){intindex=-1;char*s=abbcbasdedfadfasgdgasdfews;char*p=asgd;char*s0=CABCADCABCAABCABCABE;char*s1=CABCAABCDABCABECABCAABCABCAEBECABCAABCABCFABECABCAABACABCABECABCAABCABCABE;char*p0=CABCAABCABCABE;index=KMPMatch(s0,p0);printf(\n文本串:\n);intslen=strlen(s0);for(inti=0;islen;i++)printf(%3d,i);printf(\n);for(inti=0;islen;i++)printf(%3c,s0[i]);printf(\n\n文本串中匹配的模式串首地址i=%d\n\n,index);}intViolentMatch(char*s,char*p){intslen=strlen(s);intplen=strlen(p);inti=0;intj=0;while(islen&&jplen){if(s[i]==p[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==plen)returni-j;elsereturn-1;}voidGetNextVal(char*p,int*next){intplen=strlen(p);intj=0;intk=-1;next[0]=-1;while(jplen-1){if(k==-1||p[k]==p[j]){k++;j++;next[j]=k;}else{k=next[k];}}}voidGetNextVal2(char*p,int*next){intplen=strlen(p);intj=0;intk=-1;next[0]=-1;while(jplen-1){if(k==-1||p[k]==p[j]){k++;j++;if(p[k]!=p[j])next[j]=k;elsenext[j]=next[k];}else{k=next[k];}}}intKMPMatch(char*s,char*p){intslen=strlen(s);intplen=strlen(p);int*next=(int*)malloc(sizeof(int)*plen);GetNextVal2(p,next);printf(模式串：\n);printf(j:);for(inti=0;iplen;i++)printf(%5d,i);printf(\np[j]:);for(inti=0;iplen;i++)printf(%5c,p[i]);printf(\nnext[j]:);for(inti=0;iplen;i++)printf(%5d,next[i]);printf(\n);inti=0;intj=0;while(islen&&jplen){if(j==-1||s[i]==p[j]){i++;j++;}else{j=next[j];}}free(next);if(j==plen)returni-j;elsereturn-1;}KMP算法测试用例的演示效果及分析难点分析一：为什么要引入next数组及其作用next[j]数组存储的内容为：模式串j处字符p[j]与文本串i处字符s[i]失配时，模式串回退到的p[]数组的下标(也可以这样理解“回退”：即文本串固定，模式串右移，右移长度为j-next[j])。使p[next[j]]继续与文本串原失配处的s[i]比较，这样做的理由是模式串next[j]之前的字符串可能已经与s[i]之前且紧靠s[i]的某段字符串匹配，我们在一次的人工模拟进行匹配时，如果留意的话，很容易发现是否存在这样的某段字符串，算法自然也可以寻找出这样的一段字符串，因此我们采用next[j]数组记录模式串j下标之前，可能存在的、与紧靠s[i]之前的某段字符串匹配的字符串后一个下标（这句话虽然很拗口，但表述应该没有逻辑错误。如果p[]数组下标从0开始，next[j]也可理解为前面说的这段匹配字符串的长度，但如果很巧的出现了两处甚至多处长度不等的匹配情况，如s[i]之前是“……CABCA”，p[]数组前缀是“CABCA……”，next[j]记录最长的匹配字符串长度，这样以免回退的太远而浪费再次匹配的时间）。难点分析二：next数组的初步求法首先给出一些启发性的思考问题（见参考文献邹博老师的PPT）：1.在暴力求解中，为什么模式串的索引会回溯？因为模式串存在重复字符2.如果模式串的字符两两不相等呢？3.更弱一些的条件：如果模式串的首字符和其他字符不相等呢？如果经过仔细思考2和3的条件，会发现用这样的模式串在匹配的过程中，如果在s[i]处失配时，是不存在紧靠s[i]之前的某段字符串与模式串开头的某段字符串匹配，因为这是存在逻辑矛盾的。因此条件3给了我们求解next数组的首要启发，而且我们会发现：如果模式串中，其它地方出现一个字符与首字符相同，即匹配，再如果该字符之后的一个或一段字符也与首字符后面的一个或一段字符匹配，那么这些匹配字符后面的一个字符在匹配失配时，都可以回退到模式串前缀（一个字符或字符串）中与之匹配的字符的后面，再与文本串匹配。因此求next数组，便是寻找模式串中与前缀匹配的字符或字符串，即寻找寻找模式串中与前缀匹配的后缀（注意：它不一定是模式串的最后一个字符或字符串）。如果一个模式串中出现了不止一处与前缀匹配的后缀，且第二次匹配的长度比第一次更长，那么这样的匹配显然带有递归的性质，因此我们试着采用地推的方法，在模式串中，从前往后进行层层自匹配：如果对于值ka0a1...ak-1ak=aj-k+1...aj-1aj则对于pattern的前j+1序列字符，则若pattern[k]==pattern[j]next[j+1]=next[j]+1=k+1若pattern[k]≠pattern[j]记h=next[k],即缩小一层进行匹配；如果此时pattern[h+1]==pattern[j+1],则next[j+1]=h+1。否则，再次缩小一层进行匹配，重复此过程，直到匹配或者缩小至首字符也没匹配，此时可以确定文本串s[i]之前没有与模式串匹配的字符串，可以让i++，j=0,进行新一轮的匹配。难点分析三：next数组的进一步优化next数组记录的是回退的位置，尽量回退地一步到位，否则就是浪费时间。而next数组是递推地求出来的，因此很多情况下会出现无谓地连续回退现象。所以在模式串自匹配的过程中，如果发现前后缀匹配的两个字符，后缀字符的next值要引用前缀与之匹配字符的next值，避免无谓的连续回退。另外，“if(k==-1||p[k]==p[j]){”后面之所以没有立即执行：“next[j]=next[k];”，是为了避免k=-1时的越界错误，而先执行“k++;j++;”后，再进行判断也是不迟的，且能避免越界错误。参考文献：1.从头到尾彻底理解KMP（2014年8月22日版）2.北京7月暑假班邹博第二次课的PPT：