早就忘了，我直接搬出我6年前的問題壓縮包，解壓一遍就能再次學(xué)會。 Q1:子串從

已匹配的

第幾個開始匹配是一定會錯的呢？ A1:主串中與子串第一個字符不一樣的(廢話?) M1:每次都從主串中

已匹配的且

與子串第一個字符相等的開始吧，標記α。 M2:子串依M1執(zhí)行，假設(shè)此時子串第二個字符為β，匹配主串

已匹配部分中α后跟著的所有β，并標記β。

依次類推，直到Mi找不到匹配的字符為止，那么這個M1到Mi找到的所有標記的部分就是

已匹配部分

對應(yīng)的“最長不會錯子串” Q2:那讓你跳轉(zhuǎn)一次，你選擇跳到哪一個“最長不會錯子串” A2:最后一個。因為已經(jīng)知道“最長不會錯子串”的后一個一定是匹配不上的，唯獨最后一個的后一個字符是可能未被“考量”過的，是唯一有可能對的。 Q3:未被“考量”過的是什么情況？ A3:當

主串已匹配部分的后一個字符

成為最后一個“最長不會錯子串”的后繼字符時。 那么next數(shù)組就呼之欲出了，假如給Mi的結(jié)束條件更改為：子串找不到匹配的字符，并且該字符正好是

主串已匹配部分

的后繼字符 那么假設(shè)

已匹配部分長度

為m，“最長不會錯子串”長度為n，那么主串從子串下標為m-n-1位置繼續(xù)匹配，記錄一下next[m]=m-n-1。 那我只要把子串每前i個字符的next都算一下就行，O(P2/2):共P個字符，最好1次結(jié)束計算，最壞算一半P/2。共O(S+P2/2)≤O(SP)還行，就是沒啥進步。 顯然計算next花太多時間了，假設(shè)next[m]=m-n-1已經(jīng)手算出來了，那么next[m+1]無非就是考慮在m個已匹配字符后再加一個字符后“最長不會錯子串”的變化是啥。不妨把“最長不會錯子串”的狀態(tài)簡單分類為“變長”和“變短”，它們是兩個互斥量。 Q4:什么時候會“變長”? A4:當新加入的字符γ正好是子串下標為n的字符時，能增長一位，即 if(pattern[m-next[m]-1]==pattern[m]) next[m+1]=next[m]+1; Q5:顯然不等的時候就會變短了，變短多少？ A5:不妨剪切最后一個“最大不會錯子串”+一個后繼字符作為新的子串，原子串變?yōu)橹鞔敲匆欢ㄔ诤罄^字符處匹配失敗，而新子串后繼字符的下標就是n，此時新子串跳轉(zhuǎn)的字符個數(shù)不正是next[n]嗎(因為新子串與新主串開頭是一樣的，利用新主串算過的next數(shù)組就好) 此時新子串長度為n+1，減去next[n]再減一，就得到了一個字符的下標，n-next[n]，這個字符與后繼字符比較一下，如果相等，就讓next[m+1]=next[n-next[n]-1]+1，就像原主串和原子串的匹配一樣。 如果不相等，就又可以剪切粘貼產(chǎn)生新新子串和新新主串，也就是有一個n-next[n]-1在更新，每次更新出一個新子串長度，它的長度一定是判別字符的下標加一：n-next[n]，因此只要不等，只需要令n=n-next[n]就行。 Q6:那這個遞歸過程的出口是什么？ A6: 1.找到相等的 2.next[m]=0，此時m不會再更新遞歸死了 3.next[m]<0，next定義可知遇不到 4.next[m]＞0，可正常遞歸 綜上 else if(m-next[m]==0) next[m+1]=0 else m=m-next[m]; 換一個語義就有一種新寫法，下次我掏出這6個問題時可能會想出不同的東西。 那只需要跑一遍子串就能算完next了，O(S+P)，完成分析任務(wù)。