c語(yǔ)言字符串的模式匹配

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

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

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

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

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

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

6、,1,0}。解讀：g設(shè)定為-1o字符o之前沒有匹配的字符。o字符o（第2個(gè)）之前的字符（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）不同。舉例說(shuō)明2：模式串p=“abaabcaba”，對(duì)應(yīng)的next[j]={-1,0,0,1,1,2,0,1,2}?！綤MP算法實(shí)現(xiàn)】：第一步：求解next數(shù)組。typedefstruct{charstr[100

7、];intlength;}seqString;//根據(jù)模式t的組成求其對(duì)應(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<