數(shù)據結構第09講_串的模式匹配與串的應用_C.ppt

《數(shù)據結構第09講_串的模式匹配與串的應用_C.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、第4章串4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)4.3.2模式匹配的一種改進算法4.4串操作應用舉例4.3串的模式匹配算法4.3.1求子串位置的定位函數(shù)又稱模式匹配或串匹配，應用非常廣泛。在串匹配中，假設S為目標串，P為模式串：S=‘s1s2...sn’P=‘p1p2…pm’串的匹配實際上是根據1≤i≤n-m+1依次將S的子串S’[i..i+m-1]和P[1..m]進行比較，若S’[i..i+m-1]=P[1..m]，則稱從位置i開始的匹配成功；反之，匹配失敗。上述的位置i又稱為位移，當S’[i..i+m-1]=P[

2、1..m]時，i稱有效位移；當S’[i..i+m-1]≠P[1..m]時，i稱無效位移。這樣，串匹配問題可簡化為是找出某給定模式串P在給定目標串S中首次出現(xiàn)的有效位移。串匹配的算法很多，這里我們只討論一種最簡單的稱為樸素的串匹配算法?；舅枷耄河靡粋€循環(huán)來依次檢查n-m+1個合法的位移i(1≤i≤n-m+1)是否為有效位移。算法段：for(i=1;i<=n-m+1;i++)if(S[i..i+m-1]=P[1..m])returni;例：設pos=1；模式串T=‘abcac’例：模式匹配的算法intIndex(SStrings,SStringp,intpos){j=

3、1;i=pos;while(i<=s[0]&&j<=p[0]){if(s[i]==p[j]){i++;j++;}//繼續(xù)比較后續(xù)字符else{i=i-j+2;j=1;}//指針回溯到下一首位，重新開始匹配}if(j>p[0])returni-p[0];//匹配成功elsereturn0;}//Index相當于子串向右滑動一個字符位置匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。算法簡單并易于實現(xiàn)，但在某些情況下時間效率不高，主要的原因是主串下標i在若干個字符序列比較相等后只要有一個字符比較不相等時便需要把下標i的值回退。算法的最壞情況是：當模式串p的前

4、m-1個字符序列與主串s的相應字符序列比較總是相等，但模式串p的第m個字符與主串的相應字符比較總是不等。每次比較m個字符，比較n-m+1次，共比較m*(n-m+1)次，時間復雜度為O(n*m)。4.3.2模式匹配算法的改進算法(KMP算法)1.匹配分析KMP算法的特點主要是消除了上述算法的主串下標i在若干次字符序列比較相等后只要有一個字符比較不相等便把下標i的值回退的缺點。分析上述算法可以發(fā)現(xiàn)，算法中的主串下標i值的回退并非一定必要。我們從2種情況來分析：對于p中已與s前若干字符相匹配的部分p1～pj-1第一種情況是：模式串中不存在相等真子串的情況，即p1～pj-1

5、中不存在前k（1

6、p2=p2p3，有k=3，由于s2s3=p2p3,此時必然有s2s3=p1p2,顯然，接下來可直接比較s4和p3。總結以上2種情況可以發(fā)現(xiàn)：一旦有比較不相等時，主串s的下標不必回退，主串的si可直接和模式串的pk(1

7、abcac’Index_kmp的返回值應為i=6需要討論兩個問題：①如何“記憶”部分匹配結果？②如何由“記憶”結果計算出主串S第i個字符應該與模式T中哪個字符再比較？即確定模式T中的新比較起點k。iiikkabaabcKMP算法設計思想抓住部分匹配結果的兩個特征：兩式聯(lián)立可得：‘P1…Pk-1’=‘Pj-(k-1)…Pj-1’注意：j為當前已知的失配位置，我們的目標是計算新起點k，僅剩一個未知數(shù)k，理論上已可解，且k僅與模式串T有關！則S前i-1～i-(k-1)位＝P的j-1～j-(k-1)位即(4-3）式含義S=‘ababcabcacbab’P=‘abcac’