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

Kmp中查找一个字符串中是否包含另外一个字符串#include<>2#include<>3voidmakeNext(constcharP[],intnext[])4{5intq,k;6intm=strlen(P);7next[0]=0;8for(q=1,k=0;q<m;++q)9{10while(k>0&&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;i<n;++i)28{29while(q>0&&P[q]!=T[i])30q=next[q-1];31if(P[q]==T[i])32{33q++;34}35if(q==m)36{37printf("urswithshift:%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;i<strlen(P);++i)53{54printf("%d",next[i]);55}56printf("\n");5758return0;59} 已知前一步计算时最大相同的前后缀长度为k(k>0),即P[0]···P[k-1]; 此时比较第k项P[k]与P[q],如图1所示如果P[K]等于P[q],那么很简单跳出while循环; 关键!关键有木有!关键如果不等呢???那么我们应该利用已经得到的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那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。代码如下:#include<iostream>usingnamespacestd;intMaxSubSeq(constint*arr,intlen,int*start,int*end){intmax=0;//记录目前找到的最大子序列的和intsum=0;//记录目前子序列的和intbegin=0,finish=0;//记录目前子序列的起始下标*start=begin;*end=finish;//记录最长子序列的起始下标for(inti=0;i<len;i++){sum+=arr[i];finish=i;if(sum>max){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);cout<<"TheMaxSubSeqisfromposition"<<start<<"toposition"<<end<<"."<<endl;cout<<"SumofMaSubSeq:"<<max<<endl;return0;}最长公共子串(LCS)找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼