c語言字符串的模式匹配

《c語言字符串的模式匹配》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)面試之十四——字符串的模式匹配題注：《面試寶典》有相關(guān)習(xí)題，但思路相對不清晰，排版有錯誤，作者對此參考相關(guān)書籍和自己觀點進行了重寫，供大家參考。十四、字符串的模式匹配1.??????模式匹配定義——子串的定位操作稱為串的模式匹配。2.??????普通字符串匹配BF算法（BruteForce算法，即蠻力算法）【算法思想】：第（1）步；從主串S的第pos個字符和模式的第一個字符進行比較之，若相等，則繼續(xù)逐個比較后續(xù)字符；否則從主串的下一個字符起再重新和模式串的字符比較之。第（2）步驟；依次類推，直至模式T中的每一個字符依次和主

2、串S中的一個連續(xù)的字符序列相等，則稱匹配成功；函數(shù)值為和模式T中第一個字符相等的字符在主串S中的序號，否則稱為匹配不成功，函數(shù)值為0。比如對于主串S=”abacababc”;模式串T=”abab”;匹配成功，返回4。對于主串S=”abcabcabaac”;模式串T=”abab”;匹配不成功，返回0。?【算法實現(xiàn)】：//普通字符串匹配算法的實現(xiàn)intIndex(char*strS,char*strT,intpos){//返回strT在strS中第pos個字符后出現(xiàn)的位置。inti=pos;intj=0;intk=0;intlens=

3、strlen(strS);intlent=strlen(strT);while(i=lent){returni;}else{return0;}}//end?[算法時間復(fù)雜度]：設(shè)主串長度為m,模式串的長度為n。一般情況下n

4、n次。時間復(fù)雜度為O（n）。最壞時間復(fù)雜度：舉例，主串S=”000000000000000000001”（20個0，1個1）;模式串T=”00001”（4個0，1個1）;比較次數(shù)為17*5次。時間復(fù)雜度接近O（m*n）。整個匹配過程需要多次回溯（有16次回溯）。平均時間復(fù)雜度：O(m*n)。[空間復(fù)雜度]：O（1），不需要額外開辟空間存儲。?3.????????KMP算法?——是一種線性時間復(fù)雜的字符串匹配算法，它是對BF算法改進。[時間復(fù)雜度]：O(m+n)，即：O(strlen(S)+strlen(T))[空間復(fù)雜度]：O(n

5、)，即：O(strlen(T))【核心思想】：是利用已經(jīng)得到的部分匹配信息來進行后面的匹配過程。正文tt1t2t3?tm?tn模式pp1p2p3….pm?.?【next（j）定義】:表示當(dāng)pi不等于tr時，下一次將pnext[i]與tr開始繼續(xù)后繼對應(yīng)字符的比較。其中next[0]=-1,表明當(dāng)p0不等于tr時，將從p-1與tr開始繼續(xù)后繼對應(yīng)字符的比較；顯然p-1是不存在的，我們可以將這種情況理解成下一步將從p0與tr+1開始繼續(xù)后繼對應(yīng)字符的比較。舉例說明1：模式串p=“google”,對應(yīng)的next[j]={-1,0,0,0

6、,1,0}。解讀：g設(shè)定為-1o字符o之前沒有匹配的字符。o字符o（第2個）之前的字符（g，o）不同。g字符g之前的字符（g，o，o）前綴、后綴（如：g與o；go與oo）不匹配。l字符l之前的字符（g，o，o，g）前綴、后綴（如：g與g）相同，返回1。e字符e之前的字符（g，o，o，g，l）前綴、后綴（如：goo與ogl）不同。舉例說明2：模式串p=“abaabcaba”，對應(yīng)的next[j]={-1,0,0,1,1,2,0,1,2}?！綤MP算法實現(xiàn)】：第一步：求解next數(shù)組。typedefstruct{charstr[100

7、];intlength;}seqString;//根據(jù)模式t的組成求其對應(yīng)的next數(shù)組。voidgetNext(seqStringt,intnext[]){next[0]=-1;inti=0;intj=-1;while(i

8、

9、t.str[i]==t.str[j]){++i;++j;next[i]=j;}else{j=next[j];}}//endwhilecout<<"next["<

10、[i]<<"t";}cout<