數(shù)據(jù)結構與算法串

1、華中農業(yè)大學理學院 章 英 數(shù)據(jù)結構與算法 2/44第十講 模式匹配本講知識點：本講知識點： (1)熟悉串的模式匹配的簡單算法熟悉串的模式匹配的簡單算法 (2)掌握改進的模式匹配算法的具體實現(xiàn)掌握改進的模式匹配算法的具體實現(xiàn) (3)掌握串的應用問題掌握串的應用問題重點：重點：串的應用串的應用難點：難點：改進的模式匹配算法改進的模式匹配算法3/44在最壞情況下，第在最壞情況下，第i 趟匹配成功，前面趟匹配成功，前面i-1趟的不成功的趟的不成功的匹配中，每趟比較了匹配中，每趟比較了m次，第次，第i 趟成功時也比較了趟成功時也比較了m次次，所以共比較了，所以共比較了i m次。因此在最壞情況下，平均比

2、次。因此在最壞情況下，平均比較次數(shù)是：較次數(shù)是：由于由于nm，故上述的時間復雜度為故上述的時間復雜度為O(mn)2/ )2()1/()(1111mnmimnmmiPmnimnii匹配算法分析4/44簡單匹配算法缺點在于每次不能匹配以后主串（目標串簡單匹配算法缺點在于每次不能匹配以后主串（目標串）指針和子串（模式串）指針都必須回溯，造成了這種）指針和子串（模式串）指針都必須回溯，造成了這種算法的時間復雜度為算法的時間復雜度為O(m*n)。而而KMP算法使得主串指針不必回溯而只需回溯模式串算法使得主串指針不必回溯而只需回溯模式串指針，并且模式串指針也不一定需要回溯到模式串的第指針，并且模式串指針也

3、不一定需要回溯到模式串的第一個字符，一個字符，KMP算法的時間復雜度為算法的時間復雜度為O(m+n)。 例如，當例如，當 T=“0000000000000000000000000000001” P=“000001” 時，時，KMP算法比簡單算法效率要高的多。算法比簡單算法效率要高的多。模式匹配的改進模式匹配的改進5/44一、一、KMP算法算法 T a b a a b a b P a b a b | | |第第1趟趟 P a b a b |第第3趟趟 T a b a a b a b| P a b a b 第第2趟趟 T a b a a b a b省略第省略第2趟趟直接進行直接進行t3和和p2的比

4、較的比較6/44一、一、KMP算法算法 P a b a b T a b a a b a b|已知已知p1=t1，而，而p0p1，那么，那么p0t1由于由于p0=p2，所以，所以t2=p07/44abadabd?0taba0pdabcacbabapdabij匹配失敗匹配失敗! !基本思想基本思想8/44比較到第比較到第i+1趟匹配時，如果比較到趟匹配時，如果比較到P中第中第j個字個字符時不匹配。即：符時不匹配。即：tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpj接下來用接下來用p0和和ti+1開始比較，若匹配成功則如下開始比較，若匹配成功則如下tpti+

5、1ti+2 . ti+j ti+mp0p1 . pj-1 pm-1第第i+2趟趟9/44tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpjpp0p1 .pj-2p1p2 . pj-1p假設假設ti+1ti+2 .ti+j-1由此，第由此，第i+2趟匹配可以跳過不做。趟匹配可以跳過不做。僅考察僅考察模式串模式串分析分析10/44第第i+3趟匹配是否需要進行呢？趟匹配是否需要進行呢？tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpj假設假設模式串模式串pp0p1 .pj-3p2p3.pj-1p假設假設ti+2ti+3

6、.ti+j-1由此，第由此，第i+3趟匹配可以跳過不做。趟匹配可以跳過不做。11/44依此類推，直到對于某值依此類推，直到對于某值k，使得，使得p0p1.pk pj-k-1pj-kpj-1 而而p0p1.pk-1 = pj-kpj-k+1pj-1ti+jtiti+1.ti+j-1pp0p1.pkk+1jpj-k-1pj-k.pj-1p0p1.pk-1pj-kpj-k+1.pj-1=pki+j12/44假設主串為：假設主串為： t1t2.tn模式串為：模式串為： p1p2.pm我們要解決的問題是：當我們要解決的問題是：當“失配失配”(ti pj)時，模式時，模式串串“向右滑動向右滑動”的可行距離

7、有多遠；或者說，下一的可行距離有多遠；或者說，下一步步ti應該與模式串中的哪個字符比較應該與模式串中的哪個字符比較?可知：可知：答案將完全取決于模式串，而與主串無關答案將完全取決于模式串，而與主串無關因此：可以預先為模式串設定一個數(shù)組因此：可以預先為模式串設定一個數(shù)組nextj，當，當“失配失配”(ti pj)時，時，i不變，不變，j改為改為nextj。分析分析13/44j 0 1 2 3 4 5 6 7 模式串nextj a b a a b c a c -1 0 0 1 1 2 0 1nextj=Maxk|0kj且且P0Pk-1=Pj-kPj-k+1Pj-1 當此集合不空時當此集合不空時0

8、其他情況其他情況-1 當當j=0時時定義定義nextj例如：例如：14/44第第1趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=1j=1 next1=0第第2趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=1j=0 next0=-1第第3趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=2j=0| | | | | i=7j=5 next5=2第第4趟匹配趟匹配 T a c a b a a b

9、a a b c a c x P a b a a b c a c i=13j=8| | | | | |i=7j=2 15/44int KMPIndexHelp(const String &T, const String &P, int pos, int next ) int i=pos, j=0; while( i T.Length() & j P.Length() if ( j = -1 ) i+; j=0; else if( Pj = Ti ) i+; j+; else j = nextj; if ( j P.Length() ) return -1; else return i-j;ijn

10、extjireturn算法實現(xiàn)算法實現(xiàn)16/44可以用遞推的方法推出可以用遞推的方法推出next的值。當?shù)闹?。當j0時，時，next0=-1；設設nextj=k，即，即模式串模式串P中存在：中存在： p0p1.pk-1 = pj-kpj-k+1.pj-1其中其中k為滿足為滿足0k k滿足上式，滿足上式，因此因此nextj+1 = nextj+1 = k+1;pkjj+1計算計算next17/44abcdabcd如如next6=201234567P2P6則則next7=3舉例舉例18/44pkj2、若、若PkPj，此時可把求此時可把求nextj+1值的問題看作是一值的問題看作是一個模式匹配問題。

11、目標串和模式串都是個模式匹配問題。目標串和模式串都是P。由由nextj=k，可知：，可知： p0p1.pk-1 = pj-kpj-k+1.pj-1必須在必須在“P0P1Pk-1”中尋找使得：中尋找使得： p0p1.ph-1 = pk-hpk-h+1.pk-1 成立的最大的成立的最大的h。分兩種情況：分兩種情況：（1）找到）找到h（2）找不到）找不到h，則，則nextj+1=0h計算計算next19/44(1)若若Ph=Pj，則表明模式串，則表明模式串P中有：中有： p0p1.ph-1ph = pj-hpj-h+1.pj-1pj因此因此nextj+1 = h+1 = nextk+1=nextne

12、xtj+1;(2)若若PhPj，則再在，則再在“P0P1Ph-1”中尋找更小的中尋找更小的nexth=y。如此遞推。直到如此遞推。直到nextj+1=0，結束。，結束。pkjh計算計算next20/44j 0 1 2 3 4 5 6 7 模式串nextj a b a a b c a c-1 0 0 1 1 2 0 1已求得前已求得前6個字符的個字符的next函數(shù)值，現(xiàn)求函數(shù)值，現(xiàn)求next6。因為因為next5=2，又，又P5!=P2，則需比較，則需比較P5和和P0（因為（因為next2=0），這相當于將子串向右滑動。），這相當于將子串向右滑動。由于由于P5!=P0，而且，而且next0=-1

13、，所以，所以next6=0。而因為而因為P6=P0，則，則next7=next6+1=0+1=1。分析討論分析討論21/44void getNext(const String &P, int next ) next0 = -1; int j = 0, k = -1; while( j =0) sj+=stk-k ; sj=0; return s;算法實現(xiàn)算法實現(xiàn)40/44實戰(zhàn)練習 POJ 2503 Description You have just moved from Waterloo to a big city. The people here speak an incomprehensi

14、ble dialect of a foreign language. Fortunately, you have a dictionary to help you understand them. words 10000041/44實戰(zhàn)練習 Sample Input dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay Sample Output Cat eh loops 找不到的單詞，輸出找不到的單詞，輸出eh42/44#include#include /關聯(lián)容器 推薦看書:C+ primerusing namespace std;maptk;int main() string a,b,c; unsigned i,k,t=0; while(getline(cin,c),c.find( )!=-1) /find返回字符在串里的下標位置 k=c.fi