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

《Kmp字符串模式匹配算法.docx》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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循環(huán);4.　　關(guān)鍵！關(guān)鍵有木有！關(guān)鍵如果不等呢？？？那么我們應(yīng)該利用已經(jīng)得到的next[0]···next[k-1]來求P[0]···P[k-1]這個子串中最大相同前后綴，可能有同學(xué)要問了——為什么要求P[0]···P[k-1]的最大相同前后綴呢？？？是啊！為什么呢？?原因在于P[k]已經(jīng)和P[q]失配了，而且P[q-k]···?P[q-1]又與P[0]···P[k-1]相同，看來P[0]···P[k-1]這么長的子串是用不了了，那么我要找個同樣也是P[0]打頭、P[k-1]結(jié)尾的子串即P[0]···P[j-1](j==next[k-1])，看看它

5、的下一項P[j]是否能和P[q]匹配。如圖2所示??最大子序列最大子序列是要找出由數(shù)組成的一維數(shù)組中和最大的連續(xù)子序列。比如{5,-3,4,2}的最大子序列就是{5,-3,4,2}，它的和是8,達(dá)到最大；而{5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已經(jīng)看出來了，找最大子序列的方法很簡單，只要前i項的和還沒有小于0那么子序列就一直向后擴(kuò)展，否則丟棄之前的子序列開始新的子序列，同時我們要記下各個子序列的和，最后找到和最大的子序列。代碼如下：#includeusingnamespacestd;intMaxSubSeq(constint

6、*arr,intlen,int*start,int*end){intmax=0;//記錄目前找到的最大子序列的和intsum=0;//記錄當(dāng)前子序列的和intbegin=0,finish=0;//記錄當(dāng)前子序列的起始下標(biāo)*start=begin;*end=finish;//記錄最長子序列的起始下標(biāo)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"<