Kmp字符串模式匹配算法.doc

Kmp字符串模式匹配算法.docKmp屮杳找一个字符串中是否包含另外一个字符串#include<>#include<>voidmakeNext(constcharP[l,intnext[l)intq,k;intm=strlen(P);next[0J=0;for(q=l,k=0;q<m;++q){whilc(k>0&&P[q]!=P[k])k=next[k-l];if(P[q]==PLkJ){k++;}next[q]=k;}}intkmp(constcharT[],constcharP[],intncxt[]){intn,m;inti,q;n=strlen(T);m=(P);makeNext(Rnext);for(i=0,q=0;i<n;++i){while(q>0&&P[q]!=T[i])q=ncxt[q-1];if(P[q]==T[i]){q++;)if(q==m){printf("urswithshift:%d\n",(i-m+1));})}intmain()43{44inti;45intnext[20]={0);46charT[J=Hababxbababcadfdsss°;47charP[J="abcdabdM;48printf(”%s\n“,T);49printf(”%s\n”,P);50//makeNext(P,next);5Ikmp(T,P,next);52for(i=0;i<strlen(P);++i)53{54printf(”%dH,ncxt[i]);55}56printf(H\nH);5758return0;59}(k>0),即P[0]-P[k-1];此时比较第k项P[k]与P[q],如图1所示如果P[K]等于P[q],那么很简单跳出while循环;关键!关键有木有!关键如果不等呢???那么我们应该利用己经得到的next[0]-next[k-1]来求P[OJ-这个子串中最大相同前后缀,可能冇同学要问T——为什么要求P[0]-P[k-1]的最大相同前后缀呢???是啊!为什么呢?原因在于P[k]B经和P[q]失配了,而且P[q-k]-P[q-1]乂与P[0]-P[k-1]相同,看来P[0]-P[k-1]这么长的子串是用不了了,那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]--P[j-1](j==next[k-1]),看看它的下一项P[j]是否能和P[q]匹配。如图2所示iIIII,I I I:P[0] … P[k-1] : P[k] •―P[q]…I I I:期一步计■时 1比较;I I II I I!最大f目同的前. : :I I II I I:后缀长度为k : :图1P[0]—;P[q・k]…P[q-1]:P[q]J—MlIIPf\!P[0]…P[k-1]IP[k]!•••P[q]…丨II丨卩! P[K]•••I I II I II I II I I图2最人子序列是要找出由数组成的一维数组屮和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是{5,・3,4,2},它的和是&达到最大;而{5,・6,4,2}的最大子序列是{4,2},它的和是6。你已经看出來了,找授大了序列的方法很简单,只要前i项的和还没冇小于0那么了序列就一直向后扩展,否则丢弃Z前的子序