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

《Kmp字符串模式匹配算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Kmp中查找一个字符串中是否包含另外一个字符串#include2#include3voidmakeNext(constcharP[],intnext[])4{5intq,k;6intm=strlen(P);7next[0]=0;8for(q=1,k=0;q0&&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[]

2、)21{22intn,m;23inti,q;24n=strlen(T);25m=strlen(P);26makeNext(P,next);27for(i=0,q=0;i0&&P[q]!=T[i])30q=next[q-1];31if(P[q]==T[i])32{33q++;34}35if(q==m)36{37printf("Patternoccurswithshift:%d",(i-m+1));38}39}40}4142intmain()43{44inti;45intnext[20]={0};46charT[]="abab

3、xbababcadfdsss";47charP[]="abcdabd";48printf("%s",T);49printf("%s",P);50//makeNext(P,next);51kmp(T,P,next);52for(i=0;i0），即P[0]···P[k-1]；2.　　此时比较第k项P[k]与P[q],如图1所示3.　　如果P[K]等于P[q]，那么很

4、简单跳出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])，看看它

5、的下一项P[j]是否能和P[q]匹配。如图2所示  最大子序列最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是{5,-3,4,2}，它的和是8,达到最大；而{5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。代码如下：#includeusingnamespacestd;intMaxSubSeq(constint

6、*arr,intlen,int*start,int*end){intmax=0;//记录目前找到的最大子序列的和intsum=0;//记录当前子序列的和intbegin=0,finish=0;//记录当前子序列的起始下标*start=begin;*end=finish;//记录最长子序列的起始下标for(inti=0;imax){max=sum;*end=finish;*start=begin;}if(sum<=0){sum=0;begin=i+1;}}returnmax;}intmain(

7、){intarr[6]={5,-3,-2,12,9,-1};intstart,end;intmax=MaxSubSeq(arr,6,&start,&end);cout<<"TheMaxSubSeqisfromposition"<