Kmp字符串模式匹配算法

Kmp中查找一个字符串中是否包含另外一个字符串#includestdio.h2#includestring.h3voidmakeNext(constcharP[],intnext[])4{5intq,k;6intm=strlen(P);7next[0]=0;8for(q=1,k=0;qm;++q)9{10while(k0&&P[q]!=P[k])11k=next[k-1];12if(P[q]==P[k])13{14k++;15}16next[q]=k;17}18}1920intkmp(constcharT[],constcharP[],intnext[])21{22intn,m;23inti,q;24n=strlen(T);25m=strlen(P);26makeNext(P,next);27for(i=0,q=0;in;++i)28{29while(q0&&P[q]!=T[i])30q=next[q-1];31if(P[q]==T[i])32{33q++;34}35if(q==m)36{37printf(Patternoccurswithshift:%d\n,(i-m+1));38}39}40}4142intmain()43{44inti;45intnext[20]={0};46charT[]=ababxbababcadfdsss;47charP[]=abcdabd;48printf(%s\n,T);49printf(%s\n,P);50//makeNext(P,next);51kmp(T,P,next);52for(i=0;istrlen(P);++i)53{54printf(%d,next[i]);55}56printf(\n);5758return0;59}1.已知前一步计算时最大相同的前后缀长度为k（k0），即P[0]···P[k-1]；2.此时比较第k项P[k]与P[q],如图1所示3.如果P[K]等于P[q]，那么很简单跳出while循环;4.关键！关键有木有！关键如果不等呢？？？那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀，可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢？？？是啊！为什么呢？原因在于P[k]已经和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所示最大子序列最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是{5,-3,4,2}，它的和是8,达到最大；而{5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。代码如下：#includeiostreamusingnamespacestd;intMaxSubSeq(constint*arr,intlen,int*start,int*end){intmax=0;//记录目前找到的最大子序列的和intsum=0;//记录当前子序列的和intbegin=0,finish=0;//记录当前子序列的起始下标*start=begin;*end=finish;//记录最长子序列的起始下标for(inti=0;ilen;i++){sum+=arr[i];finish=i;if(summax){max=sum;*end=finish;*start=begin;}if(sum=0){sum=0;begin=i+1;}}returnmax;}intmain(){intarr[6]={5,-3,-2,12,9,-1};intstart,end;intmax=MaxSubSeq(arr,6,&start,&end);coutTheMaxSubSeqisfrompositionstarttopositionend.endl;coutSumofMaSubSeq:maxendl;return0;}最长公共子串（LCS）找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧：bab和caba(当然我们现在一眼就可以看出来最长公共子串是ba或ab)babc000a010b101a010我们看矩阵的斜对角线最长的那个就能找出最长公共子串。不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。babc000a010b102a020这样矩阵中的最大元素就是最长公共子串的长度。在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。代码如下：#includeiostream#includecstring#includevectorusingnamespacestd;//str1为横向，str2这纵向conststringLCS(conststring&str1,conststring&str2){intxlen=str1.size();//横向长度vectorinttmp(xlen);//保存矩阵的上一行vectorintarr(tmp);//当前行intylen=str2.size();//纵向长度intmaxele=0;//矩阵元素中的最大值intpos=0;//矩阵元素最大值出现在第几列for(inti=0;iylen;i++){strings=str2.substr(i,1);arr.assign(xlen,0);//数组清0for(intj=0;jxlen;j++){if(str1.compare(j,1,s)==0){if(j==0)arr[j]=1;elsearr[j]=tmp[j-1]+1;if(arr[j]maxele){maxele=arr[j];pos=j;}}}//{//vectorint::iteratoriter=arr.begin();//while(iter!=arr.end())//cout*iter++;//coutendl;//}tmp.assign(arr.begin(),arr.end());}stringres=str1.substr(pos-maxele+1,maxele);returnres;}intmain(){stringstr1(21232523311324);stringstr2(312123223445);stringlcs=LCS(str1,str2);coutlcsendl;return0;}最长公共子序列最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程：等号约定，C1是S1的最右侧字符，C2是S2的最右侧字符，S1‘是从S1中去除C1的部分，S2'是从S2中去除C2的部分。LCS(S1,S2)等于下列3项的最大者：（1）LCS（S1，S2’）（2）LCS（S1’，S2）（3）LCS（S1’，S2’）--如果C1不等于C2；LCS（S1'，S2'）+C1--如果C1等于C2；边界终止条件：如果S1和S2都是空串，则结果也是空串。下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应，矩阵中每个格子里的数字应该这么填，它等于以下3项的最大值：（1）上面一个格子里的数字（2）左边一个格子里的数字（3）左上角那个格子里的数字（如果C1不等于C2）；左上角那个格子里的数字+1（如果C1等于C2）举个例子GCTA00000G01111B01111T01122A01123填写最后一个数字时，它应该是下面三个的最大者：（1）上边的数字2（2）左边的数字2（3）左上角的数字2+1=3,因为此时C1==C2所以最终结果是3。在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格，以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大，那么任取其中之一，但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上左上。下图给出了回溯法找出LCS的过程：最大子序列、最长公共子串、最长公共子序列奉上代码：#includeiostream#includecstring#includestack#includeutility#defineLEFTUP0#defineLEFT1#defineUP2usingnamespacestd;intMax(inta,intb,intc,int*max){//找最大者时a的优先级别最高，c的最低.最大值保存在*max中intres=0;//res记录来自于哪个单元格*max=a;if(b*max){*max=b;res=1;}if(c*max){*max=c;res=2;}returnres;}//调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。stringLCS(conststring&str1,conststring&str2){intxlen=str1.size();//横向长度intylen=str2.size();//纵向长度if(xlen==0||ylen==0)//str1和str2中只要有一个为空，则返回空return;pairint,intarr[ylen+1][xlen+1];//构造pair二维数组，first记录数据，second记录来源for(inti=0;i=xlen;i++)//首行清0arr[0][i].first=0;for(intj=0;j=ylen;j++)//首列清0arr[j][0].first=0;for(inti=1;i=ylen;i++){chars=str2.at(i-1);for(intj=1;j=xlen;j++){intleftup=arr[i-1][j-1].first;intleft=arr[i][j-1].first;intup=arr[i-1][j].first;if(str1.at(j-1)==s)//C1==C2leftup++;intmax;arr[i][j].second=Max(leftup,left,up,&arr[i][j].first);//coutarr[i][j].firstarr[i][j].second;}//coutendl;}//回溯找出最长公共子序列stackintst;inti=ylen,j=xlen;while(!(i==0&&j==0)){if(arr[i][j].second==LEFTUP){if(arr[i][j].first==arr[i-1][j-1].first+1)st.push(i);--i;--j;}elseif(arr[i][j].second==LEFT){--j;}elseif(arr[i][j].second==UP){--i;}}stringres=;while(!st.empty()){intindex=st.top()-