數(shù)據(jù)結(jié)構(gòu)—串的模式匹配.doc

《數(shù)據(jù)結(jié)構(gòu)—串的模式匹配.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實驗一串的模式匹配1.程序設(shè)計簡介為簡化設(shè)計，程序直接利用C++字符數(shù)組作為串的存儲結(jié)構(gòu)。程序提供顯示串（包含主串和模式串）、計算Next[]、BF匹配、KMP匹配、重建主串、重建模式串等功能。2.源代碼//串模式匹配的類定義FindSub.cpp#include#include#include#include#includeconstmaxsize=30;intIndexBF(chars[],chart[],i

2、ntpos){inti,j,m,n;i=pos-1;j=0;m=strlen(s);n=strlen(t);while(i=n)returni-n+1;elsereturn-1;}voidGetNext(chart[],intnext[]){//求模式串T的next函數(shù)值并存入數(shù)組nextintj=0,k=-1;intn=strlen(t);next[j]=-1;while(j

3、=-1

4、

5、t[j]==t[k]){j++;k++;next[j]=k;}elsek=next[k];}}intIndexKMP(chars[],chart[],intnext[],intpos){//利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置的KMP算法。//其中,T非空,1≤pos≤StrLength(S)inti,j,n;i=pos-1;j=0;intm=strlen(s);//s[m]='