)
1. 為什么把三個算法放在一講最近在整理經典算法題精講系列這一講比較特殊把Manacher算法、bfprt算法、KMP算法放在了一起。乍一看這三個東西八竿子打不著——一個管回文串一個管TopK一個管字符串匹配。但把它們放一起講是有道理的因為它們共享同一個核心命題如何把暴力解法優(yōu)化到線性復雜度。先從各自的戰(zhàn)場說起。KMP算法解決的是字符串匹配問題就是在一個長文本里找一個模式串是否出現、出現在哪。暴力做法是拿模式串逐位對齊主串失配就右移一位重新比較最壞復雜度O(n*m)。KMP的精髓在于失配時不回退主串指針只利用已匹配部分的信息快速移動模式串把匹配過程壓到O(nm)。Manacher算法解決的是最長回文子串問題。回文串是正著讀倒著讀都一樣的字符串比如aba、abba。暴力解法以每個字符為中心向兩邊擴展復雜度O(n2)。Manacher利用回文的鏡像對稱性質在擴展過程中復用已經算過的回文半徑信息把復雜度降到O(n)。bfprt算法解決的是無序數組中找第K小或第K大元素的問題。常規(guī)思路是用快速排序的partition做隨機選擇期望O(n)但最壞退化到O(n2)。bfprt是一套確定性的選主元策略保證每次partition都能淘汰足夠多的元素從數學上證明最壞也是O(n)。這五個字母來自Blum、Floyd、Pratt、Rivest、Tarjan五位作者的名字所以也叫中位數的中位數算法。這三個算法在面試和競賽中的出場率很高但很多人對它們的理解停留在背模板層面換個場景就懵。比如KMP的next數組求法江湖上有至少三種定義方式網上教程各寫各的初學者很容易繞暈。比如Manacher的對稱性優(yōu)化邊界情況處理錯一位整個結果就崩。再比如bfprt問為什么必須是5個一組能答上來的人真不多大多數只是機械地照著代碼抄。這篇是先講KMP和Manacherbfprt的完整版本放在下一篇展開。之所以這么安排是因為KMP的next數組演示了信息復用這個思想的最基礎形態(tài)Manacher則在這個思想上加了一層對稱性的巧勁bfprt又把它延伸到確定性選主元的方向。三個算法放在一起看能明顯感受到算法優(yōu)化的一條主線想辦法利用已有的計算結果避免重復勞動。下面先把KMP掰開揉碎講清楚再講Manacher。整個過程我盡量用當初我學的時候踩過的坑的視角來寫配合完整的Java實現代碼最后附上刷題時常見的幾個問題排查思路。2. KMP算法next數組是靈魂2.1 從BF算法到KMP到底優(yōu)化了什么先明確一點KMP解決的是單模式串匹配問題。給定一個主串S和一個模式串P要在S中找到P第一次出現的位置。最原始的做法叫BF算法Brute Force也叫樸素匹配。BF的做法從S的每個位置i出發(fā)拿P逐位對齊比較。如果某一位失配就把P整體右移一位從P的第0位重新開始比較。public static int bfSearch(String s, String p) { int n s.length(), m p.length(); for (int i 0; i m n; i) { int j 0; while (j m s.charAt(i j) p.charAt(j)) { j; } if (j m) { return i; } } return -1; }這段代碼邏輯沒錯問題出在效率上。假設S是aaaaaaaaaaaaaaaaabP是aaab每次都要比較到P的最后一位才發(fā)現失配然后i只前進一位。整體下來近似比較nm次復雜度O(nm)。仔細想想BF到底浪費了什么信息答案是已經匹配成功的那一段被白白丟掉了。舉個例子SababcabcabababdPababd。當P的前4位abab都匹配成功第5位P[4]d與主串中的c失配時我們能從這個4位已經匹配的事實中推導出什么P的前綴abab有長度為2的公共前后綴ab這意味著如果把P右移2位P的前綴ab依然能和主串當前位置之前的ab對上。這個結論只需要分析P自己就能得到不需要知道主串的任何額外信息。KMP的核心思想就用一句話概括失配時利用模式串自身的結構信息把模式串一次性右移到可能匹配的最遠位置主串指針絕不回退。這里的模式串自身的結構信息就是next數組。2.2 next數組的兩種定義方式別再混了網上講KMP的教程next數組的定義有無數種版本本質都是最長公共前后綴長度但在具體實現上差一位。先明確一個基礎概念對于一個字符串它的前綴是去掉末尾若干字符后得到的子串后綴是去掉開頭若干字符后得到的子串。所謂最長公共前后綴就是既是前綴又是后綴的最長子串長度且這個子串不能是字符串本身也不能是空串。比如ababa長度為1的前后綴a和a相等匹配長度為1長度為2的前后綴ab和ba不等長度為3的前后綴aba和aba相等匹配長度為3長度為4的前后綴abab和baba不等所以ababa的最長公共前后綴長度是3。網上常見的next數組定義有兩種定義Anext[i]表示模式串P的[0, i)子串即P[0..i-1]的最長公共前后綴長度也就是中文教程里常說的前綴函數。這里的next[0]-1有些約定為0表示空串沒有公共前后綴。定義Bnext[i]表示模式串P的[0, i]子串即P[0..i]的最長公共前后綴長度即next[i]對應的是包含第i個字符在內的子串。兩種定義各有擁護者計算出來的next數組整體錯一位但匹配時的跳轉邏輯也相應調整。KMP本身沒有歧義算法是正確的歧義全在next數組的具體約定上。這篇文章里我采用題目中給出的定義來規(guī)定next[i]定義為模式串p[0..i-1]的最長公共前后綴長度不過next[0]我習慣設為-1用-1作為公共前后綴不存在的哨兵。為了避免歧義下面直接用具體例子說明。2.3 手算abacaba的next數組看題目里的例子模式串Pabacaba按照next[i]定義為p[0..i-1]的最長公共前后綴長度來計算。先拆開看每個前綴子串i0: 空串next[0] -1 i1: p[0]a最長公共前后綴長度為0next[1] 0 i2: p[0..1]ab前綴a后綴b不等next[2] 0 i3: p[0..2]aba前綴a后綴a長度1更長的不行next[3] 1 i4: p[0..3]abaca和c不等next[4] 0 i5: p[0..4]abaca前綴a后綴a長度1前綴ab和后綴ca不等next[5] 1 i6: p[0..5]abacab前綴ab后綴ab長度2aba和cab不等next[6] 2 i7: p[0..6]abacaba前綴aba后綴aba長度3next[7] 3所以得到i01234567next[i]-10010123這里的next[7]是最后用到的值嗎不一定。如果匹配到P最后一位失敗了需要跳轉到next[7]3也就是說明前7位都匹配上了但第8位失配此時模式串最長公共前后綴長度為3所以從下標3繼續(xù)嘗試。理解這個表之后再來看代碼實現。求next數組的代碼經典寫法如下public static int[] getNext(String p) { int m p.length(); int[] next new int[m 1]; next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p.charAt(i) p.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; }這段代碼的核心邏輯是用兩個指針i和jj代表已經匹配上的公共前后綴長度。如果p[i]p[j]說明公共前后綴可以延長一位繼續(xù)如果失配j就回退到next[j]相當于在計算next數組的過程中也要用到next數組自身的跳轉信息這就是遞歸地利用已計算的信息。有個細節(jié)值得注意next數組長度是m1而不是m因為按照定義Anext[m]是完整的P[0..m-1]的最長公共前后綴長度匹配過程中模式串走到頭時也要查這個值。2.4 KMP匹配過程主串指針不回退有了next數組匹配邏輯就順理成章了。public static int kmpSearch(String s, String p) { int n s.length(), m p.length(); if (m 0) return 0; int[] next getNext(p); int i 0, j 0; while (i n) { if (j -1 || s.charAt(i) p.charAt(j)) { i; j; } else { j next[j]; } if (j m) { return i - m; } } return -1; }匹配時最關鍵的跳轉分支是else當s[i] ! p[j]時主串下標i不動只把模式串下標j更新為next[j]。這里next[j]的含義是前j個字符已經匹配相同時最長公共前后綴的長度所以模式串跳到該長度處繼續(xù)比較而主串當前位置之前的那些字符已經保證與模式串前綴對齊了。用生活類比理解你在書里查找一個詞當連續(xù)幾頁都符合關鍵詞前綴突然某一頁對不上時你不會回到書的第一頁重查而是根據已經匹配到的部分把關鍵詞的某個前綴對齊到當前頁繼續(xù)往后翻。主串就好比書頁只有前進沒有后退模式串的移動靠next數組來指導。來看一個具體的匹配例子。主串Sababacabacaba模式串Pabacaba。i0j0s[0]a與p[0]a匹配i1j1i1j1s[1]b與p[1]b匹配i2j2i2j2s[2]a與p[2]a匹配i3j3i3j3s[3]b與p[3]c失配j跳到next[3]1主串不前進i3j1s[3]b與p[1]b匹配i4j2i4j2s[4]a與p[2]a匹配i5j3i5j3s[5]c與p[3]c匹配i6j4i6j4s[6]a與p[4]a匹配i7j5i7j5s[7]b與p[5]b匹配i8j6i8j6s[8]a與p[6]a匹配i9j7jm返回i-m2主串從位置2開始匹配成功即子串abacaba出現在S[2..8]位置。注意在第4步主串index3處的失配i沒有回退到1而是原地等待模式串通過next跳轉后繼續(xù)比較。這就是KMP主串不回退的直觀體現。KMP的時間復雜度為什么是O(nm)匹配過程中i只會增加不會減少最多增加n次j每次失配時通過next跳轉會變小但j增加的次數不超過i增加的次數每次匹配成功j加1匹配失敗j減少但總量有限整體均攤下來代價是線性的。求next數組同理i和j的移動次數也是O(m)。所以最終是O(nm)。2.5 KMP的應用遠不止字符串匹配很多初學者覺得KMP只能用來做文本里的子串查找其實它的應用面比想象中寬。第一個實用場景是判斷一個字符串是否是另一個字符串的循環(huán)移位。比如判斷B是否是A的循環(huán)移位常規(guī)思路是AA拼起來看B在AA中是否出現。這本質就是一次KMP匹配。第二個場景是求字符串的最短重復周期。給一個字符串s如果它可以由某個子串重復k次構成找出這個最小周期子串。結論是用KMP求出next數組后答案是n - next[n]如果n % (n - next[n]) 0那么這個最短重復周期長度就是n - next[n]。這個結論在很多字符串題里是隱藏考點。第三個場景是KMP自動機思想。把KMP的匹配過程理解成模式串在不同狀態(tài)之間跳轉這就是有限狀態(tài)自動機的雛形。AC自動機多模式串匹配、最大長度前綴匹配等進階算法都建立在這個思想上。所以說KMP不是孤立的一個小技巧它是很多字符串數據結構的底層地基。提示刷題時如果遇到判斷子串是否出現求最短周期循環(huán)移位這類描述第一反應應該是KMP或KMP的變形而不是直接上暴力。3. Manacher算法最長回文子串的線性解法3.1 回文問題的暴力解法為什么慢KMP講清楚了來看Manacher。這個算法解決的是最長回文子串問題比如給定字符串babad最長回文子串是bab或aba長度3。暴力解法有兩種思路。第一種是枚舉所有子串逐個判斷是否回文復雜度O(n3)基本屬于不可用。第二種是中心擴展法枚舉每個位置作為回文中心向兩邊擴展直到不能擴展為止記錄最長的回文長度。public static String longestPalindrome(String s) { if (s null || s.length() 1) return ; int start 0, maxLen 1; for (int i 0; i s.length(); i) { int len1 expand(s, i, i); // 奇數長度回文 int len2 expand(s, i, i 1); // 偶數長度回文 int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private static int expand(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }中心擴展法的時間復雜度是O(n2)在字符串長度幾百萬級別時完全跑不動。Manacher算法的目標是把復雜度壓到O(n)。它的核心優(yōu)化只有一條當我們要計算某個位置的回文半徑時如果這個位置位于之前某個大回文的內部那么可以利用回文的對稱性直接借用對稱位置的已知回文半徑作為初始值省去從1開始擴展的過程。3.2 鏡像對稱Manacher最巧妙的優(yōu)化要理解Manacher先弄明白四個變量C當前已知的回文串的中心位置R當前已知的回文串的最右邊界R右邊那個位置表示半徑覆蓋到R-1P[i]以位置i為中心的回文半徑包含中心本身mirror 2*C - ii關于C的對稱位置算法的核心邏輯是如果i在R的范圍內即i R那么P[i]至少等于min(P[mirror], R - i)。為什么因為i和mirror關于C對稱而C的回文范圍[R的左邊界, R]是對稱的。既然以C為中心的回文包含了i和mirror那么mirror回文半徑里的內容在i的鏡像位置上一定也是對稱的。所以P[i]可以直接從P[mirror]繼承這是Manacher的加速核心。但有個限制條件P[i]不能超過R-i因為一旦超過R就超出了C的回文覆蓋范圍這個范圍之外的對稱性就無法保證了。所以取min(P[mirror], R - i)。如果i在R之外沒有對稱信息可用P[i]初始為1。這里有一個關鍵問題回文半徑的奇偶性怎么處理回文串有兩種情況奇數長度如aba中心是單個字符b偶數長度如abba中心在bb之間。直接處理時需要區(qū)分兩種情況代碼寫起來麻煩而且P數組在不同情況下含義不一致。Manacher的經典做法是在原始字符串的每個字符之間包括首尾插入一個特殊字符比如把aba改寫成#a#b#a#把abba改寫成#a#b#b#a#。插入后原來的奇數回文和偶數回文都統一成了奇數回文以特殊字符為中心或普通字符為中心處理起來就不需要分支判斷了。這里的特殊字符可以是任何不沖突的字符比如#因為它不會與原始字符匹配。原始字符串s長度為n變換后的字符串t長度為2n1。求得的P[i]是t中以i為中心的回文半徑對應到原始字符串的回文長度就是P[i]-1。最終答案就是所有P[i]中的最大值減1。3.3 Manacher的完整實現與邊界分析直接看代碼public static String manacher(String s) { if (s null || s.length() 0) return ; // 構造帶分隔符的字符串 char[] chars new char[s.length() * 2 1]; int idx 0; for (int i 0; i chars.length; i) { chars[i] (i % 2 0) ? # : s.charAt(idx); } int n chars.length; int[] p new int[n]; int C 0, R 0; int maxLen 0, maxCenter 0; for (int i 0; i n; i) { // 利用對稱性初始化 p[i] if (i R) { int mirror 2 * C - i; p[i] Math.min(p[mirror], R - i); } else { p[i] 1; } // 中心擴展 while (i - p[i] 0 i p[i] n chars[i - p[i]] chars[i p[i]]) { p[i]; } // 更新 C 和 R if (i p[i] R) { C i; R i p[i]; } // 記錄最大長度 if (p[i] - 1 maxLen) { maxLen p[i] - 1; maxCenter i; } } // 根據中心位置還原原始字符串 int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen); }逐行拆解第一步構造帶分隔符的數組。偶數位放#奇數位放原始字符注意chars[1]是s[0]chars[3]是s[1]以此類推。第二步初始化P[i]。當i R時用對稱性預填一個初始值這樣while循環(huán)的擴展次數被大大壓縮。當i R時沒有對稱信息可用初始為1。第三步中心擴展。這個while循環(huán)看起來和暴力中心擴展一樣但它的執(zhí)行次數已經被前面的初始化大幅削減。注意邊界條件i - p[i] 0 和 i p[i] n防止數組越界。第四步更新C和R。C和R的更新原則是一旦發(fā)現當前位置的最右邊界超過了原來的R就更新R和C。這保證了后續(xù)位置盡量多的i能夠落在R的范圍內從而利用鏡像優(yōu)化。第五步記錄最大長度。maxLen p[i] - 1對應原始字符串的回文長度。還原原始字符串的下標時有一個小技巧maxCenter是變換后數組中的中心下標maxLen是原始回文長度那么原始字符串起始位置是(maxCenter - maxLen) / 2。這個公式可以自己推一下變換后的字符到原始字符的下標映射關系是rawIndex transformedIndex / 2因為插入字符占了一半位置回文在變換后數組中的區(qū)間是[maxCenter - maxLen, maxCenter maxLen]除2后對應的原始區(qū)間起點就是(maxCenter - maxLen) / 2。3.4 復雜度分析和幾個容易踩的坑Manacher的復雜度為什么是O(n)看似while循環(huán)里有一層嵌套但是注意每次while擴展都會使R向右移動而R在整個算法過程中只會向右移動最多移動n次。所以while循環(huán)的總執(zhí)行次數是O(n)的。P數組的初始化、C和R的更新都是O(1)操作總的循環(huán)次數n次所以整體是O(n)。實際操作中有幾個坑我在這里集中說一下第一個坑是分隔符的選擇。用#是慣例但要求這個字符不能出現在原始字符串里否則會干擾匹配。比如原始字符串里有#你還用#做分隔符整個算法的正確性就被破壞了。穩(wěn)妥做法是選一個不影響判斷的字符或者明確知道原始字符集范圍。第二個坑是P[i]的初始值。我見過很多人把p[i]初始化寫成0然后while循環(huán)里從i開始擴展這樣就會漏掉單個字符的回文情況導致邊界問題。記住p[i]至少是1因為單個字符本身是回文。第三個坑是還原原始字符串下標時容易算錯。直接用原始思路推導會快很多別死記公式推一遍就懂。第四個坑是C和R的更新時機。只有當i p[i] R時才更新等于不更新。因為等于的時候新的回文半徑沒有超出已有覆蓋范圍不需要調整。注意Manacher求的是最長回文子串的長度或者具體子串。如果題目只需要長度可以精簡掉字符串還原部分只保留maxLen的計算。Manacher在高頻面試題中的出現率很高尤其是字節(jié)、快手的算法題庫里最長回文子串幾乎是標配題用Manacher寫成O(n)級別面試官的印象分會比O(n2)高不少。4. bfprt算法確定性搞定TopK問題4.1 TopK問題為什么難在最壞情況前兩個算法都講完了最后說bfprt。整體安排在下一篇展開但核心思路和代碼框架值得先在這里鋪墊一下方便大家把三個算法串起來理解。問題定義給定一個無序數組找出第K小或第K大的元素。比如[3, 2, 1, 5, 6, 4]K2時答案是2排序后為[1,2,3,4,5,6]第2小是2。最簡單的做法是排序后取第K個復雜度O(n log n)。但這個問題比排序更簡單不需要完全有序所以期望做到O(n)。常見的優(yōu)化方案是快速選擇QuickSelect利用快速排序的partition思想每次選取一個pivot把數組分成小于pivot和大于pivot兩部分。如果pivot的位置恰好是K直接返回否則在左半邊或右半邊遞歸。隨機選pivot時期望復雜度是O(n)但最壞情況下每次選到最大或最小元素遞歸規(guī)模每次只減少1復雜度退化為O(n2)。bfprt算法要解決的就是這個最壞情況它通過一種確定性的pivot選擇策略保證無論輸入數據長什么樣復雜度都能控制在O(n)。4.2 中位數的中位數五個一組的原因bfprt的核心是中位數的中位數選主元思路整個過程分五步將數組按每5個元素一組分組最后一組不足5個也單獨成組對每組內的元素排序組內最多5個用插入排序即可取出每組的中位數放到一個新的數組中遞歸調用bfprt求這個中位數數組的中位數把它作為pivot用pivot對原數組做partition根據partition后的位置判斷是在左邊找還是在右邊找遞歸處理為什么必須是5個一組這是bfprt算法中最核心的證明點。假設數組有n個元素5個一組共有n/5組近似。每組內部排序后取中位數由于每組有5個元素中位數是第3個即每組有2個元素小于等于該組中位數2個元素大于等于。這些中位數的中位數記為pivot。那么有多少元素能確定小于pivot有一半的組的中位數小于等于pivot因為pivot是中位數的中位數這些組各有2個元素小于等于該組中位數所以這些組的至少3個元素小于等于pivot該組中位數本身加上2個更小的。粗略估算有約(n/10)*3 3n/10個元素一定小于pivot。同理約3n/10個元素一定大于pivot。所以partition之后最壞情況下遞歸處理的子問題規(guī)模不超過7n/10。由此得到遞歸式T(n) ≤ T(n/5) T(7n/10) O(n)其中T(n/5)是求中位數的中位數的時間T(7n/10)是遞歸查找的時間O(n)是分組、排序、partition的時間。解這個遞歸式最終得到T(n) O(n)。用替代法可以直接證明。為什么不用3個一組3個一組的話每組中位數以上的元素有2個有一半組的中位數小于pivot所以能確定小于pivot的元素約(n/6)*2 n/3遞歸規(guī)模變?yōu)?n/3遞歸式變?yōu)門(n) ≤ T(n/3) T(2n/3) O(n)這個式子解出來是O(n log n)無法保證線性。7個一組可以但分組排序的常數更大實際運行更慢。5個一組是數學證明和工程效率的平衡點。4.3 bfprt的確定性為什么重要bfprt相對QuickSelect的優(yōu)勢是確定性。QuickSelect依賴隨機性雖然期望復雜度是O(n)但在某些特定輸入下比如數組已經有序且每次pivot都選到最小值會退化。bfprt不依賴數據分布無論輸入什么都能保證O(n)。但是這里要說不中聽的話bfprt的常數特別大每次遞歸都要分組、組內排序、求中位數數組的中位數實際運行時間可能比QuickSelect慢好幾倍。所以它在工程中很少直接使用更多是作為理論工具出現。比如在算法課上證明選擇問題存在確定性線性算法或者在某些實時系統里要求最壞情況可控的場景。面試中如果被問到建議這樣回答先說bfprt是確定性O(n)的TopK算法再說五步流程最后強調5個一組的原因——保證每次partition至少刪除3n/10個元素遞歸規(guī)模最多7n/10最終解出O(n)。完整代碼實現、變種問題和復雜度的嚴格數學證明我放在下一篇寫。這里先給出一個簡單的Java框架方便對照理解public static int bfprt(int[] arr, int k) { // k從1開始計數 return bfprt(arr, 0, arr.length - 1, k - 1); } private static int bfprt(int[] arr, int left, int right, int k) { if (left right) return arr[left]; int pivot medianOfMedians(arr, left, right); int[] range partition(arr, left, right, pivot); if (k range[0] k range[1]) { return arr[k]; } else if (k range[0]) { return bfprt(arr, left, range[0] - 1, k); } else { return bfprt(arr, range[1] 1, right, k); } }這里的medianOfMedians對應上面說的選主元邏輯partition是荷蘭國旗問題的三路快排寫法。等下篇再展開。5. 常見問題與排查技巧實錄5.1 KMP next數組求錯的排查思路KMP寫出來跑一遍結果不對90%的情況是next數組求錯了。排查時按以下步驟走第一步對照你采用的next定義手算幾個簡單串的結果比如aaaa、abab、abcabc看看你的代碼輸出是什么。如果手算和代碼不一致說明理解或實現有一方出了問題。第二步重點檢查求next的循環(huán)邊界。while循環(huán)的終止條件、i和j的初始值、next[i]賦值時機這三處最容易錯。比如忘了next[0]-1或者在失配時回退j寫成j--而不是jnext[j]都會導致結果偏差。第三步打印匹配過程的中間變量。在kmpSearch的else分支里打印i和j的值觀察主串指針是否真的沒有回退模式串跳轉是否和手算一致。我見過一個典型錯誤定義A和定義B混用。求next時用定義Anext[i]p[0..i-1]的最長公共前后綴但匹配跳轉時卻按定義B的邏輯來。雖然只是差一位但最終的匹配結果完全不對。5.2 Manacher邊界問題排查Manacher代碼不長但邊界問題非常隱蔽。如果你發(fā)現結果差一位或者偶數字符串處理錯先檢查以下幾點第一檢查構造的變換數組是否正確。下標0放#下標1放s[0]下標3放s[1]這個映射錯了整個算法全崩?？梢韵却蛴∽儞Q后的字符數組肉眼核對。第二檢查while循環(huán)的邊界條件。i - p[i] 0和i p[i] n這兩個條件缺一不可少寫一個就會數組越界。第三檢查還原回文子串的公式。之前提到start (maxCenter - maxLen) / 2這里maxCenter是變換后數組的下標maxLen是原始回文長度。如果你用p[i]直接當作原始長度還原出的字符串就是錯的。第四檢查空串和單字符的邊界情況?？沾苯臃祷乜諉巫址祷刈陨磉@兩個case要單獨處理。5.3 面試中的常見追問與應對思路這三個算法在面試中只會寫代碼是不夠的很可能被追問到原理層面的問題。對于KMP面試官最常問的是next數組怎么來的為什么時間復雜度是O(n)next[j]回退時為什么不會漏掉可能的匹配回答時抓住主串指針不回退和利用模式串自身的最長公共前后綴信息這兩個核心就行。對于Manacher高頻追問是為什么插入分隔符后能統一奇偶為什么P[i]的初始值取min(P[mirror], R-i)復雜度的直觀解釋是什么回答時記得強調超過R的部分對稱性無法保證所以必須取min這個關鍵點。對于bfprt高頻追問是為什么是5個一組3個一組行不行怎么證明復雜度是O(n)回答時把遞歸式和分組淘汰比例講清楚基本就能過。還有一個小技巧面試時如果寫了bfprt可以先說一句這個算法常數比較大實際工程中通常用隨機化QuickSelect但bfprt的優(yōu)勢是確定性O(n)。這句話能體現你對算法有整體認知而不僅僅是背了模板。6. 三個算法的共同主線把KMP、Manacher、bfprt放一起講完再回頭看它們的聯系。KMP的next數組是利用已匹配部分的公共前后綴信息避免主串回退Manacher的P數組是利用回文的鏡像對稱性避免重復擴展bfprt是分組取中位數再取中位數的中位數避免partition選到極端pivot。三個算法從不同的角度驗證了同一個道理算法優(yōu)化的本質是信息的最大化復用以及最壞情況的主動規(guī)避。這個道理應用到實際開發(fā)中很多性能問題都能找到優(yōu)化思路。比如處理字符串時如果發(fā)現某些子串被反復計算就要考慮預處理記憶化處理大數據時如果某種選主元策略在極端輸入下會退化就要考慮更穩(wěn)妥的確定性策略。下一篇會展開bfprt的完整實現包括每組排序代碼、中位數數組的遞歸處理、partition的三路劃分以及幾個變種題目第K大、找中位數、找出所有TopK元素的解法。到時候拿到代碼建議先自己跑一遍再試著改一改比單純看一遍印象深得多。我自己帶過的學員里很多人卡在這三個算法上是因為眼高手低——看講解都覺得懂了一寫代碼就各種邊界問題。所以這里多說一句算法這東西看一百遍不如手寫五遍寫完再對著測試用例跑尤其要把剛才說的邊界情況全部測一遍。這個過程不是浪費時間而是真正把別人的解法變成自己的內功。 KMP、Manacher、bfprt三大線性算法精講：從暴力到最優(yōu)
1. 為什么把三個算法放在一講最近在整理經典算法題精講系列這一講比較特殊把Manacher算法、bfprt算法、KMP算法放在了一起。乍一看這三個東西八竿子打不著——一個管回文串一個管TopK一個管字符串匹配。但把它們放一起講是有道理的因為它們共享同一個核心命題如何把暴力解法優(yōu)化到線性復雜度。先從各自的戰(zhàn)場說起。KMP算法解決的是字符串匹配問題就是在一個長文本里找一個模式串是否出現、出現在哪。暴力做法是拿模式串逐位對齊主串失配就右移一位重新比較最壞復雜度O(n*m)。KMP的精髓在于失配時不回退主串指針只利用已匹配部分的信息快速移動模式串把匹配過程壓到O(nm)。Manacher算法解決的是最長回文子串問題。回文串是正著讀倒著讀都一樣的字符串比如aba、abba。暴力解法以每個字符為中心向兩邊擴展復雜度O(n2)。Manacher利用回文的鏡像對稱性質在擴展過程中復用已經算過的回文半徑信息把復雜度降到O(n)。bfprt算法解決的是無序數組中找第K小或第K大元素的問題。常規(guī)思路是用快速排序的partition做隨機選擇期望O(n)但最壞退化到O(n2)。bfprt是一套確定性的選主元策略保證每次partition都能淘汰足夠多的元素從數學上證明最壞也是O(n)。這五個字母來自Blum、Floyd、Pratt、Rivest、Tarjan五位作者的名字所以也叫中位數的中位數算法。這三個算法在面試和競賽中的出場率很高但很多人對它們的理解停留在背模板層面換個場景就懵。比如KMP的next數組求法江湖上有至少三種定義方式網上教程各寫各的初學者很容易繞暈。比如Manacher的對稱性優(yōu)化邊界情況處理錯一位整個結果就崩。再比如bfprt問為什么必須是5個一組能答上來的人真不多大多數只是機械地照著代碼抄。這篇是先講KMP和Manacherbfprt的完整版本放在下一篇展開。之所以這么安排是因為KMP的next數組演示了信息復用這個思想的最基礎形態(tài)Manacher則在這個思想上加了一層對稱性的巧勁bfprt又把它延伸到確定性選主元的方向。三個算法放在一起看能明顯感受到算法優(yōu)化的一條主線想辦法利用已有的計算結果避免重復勞動。下面先把KMP掰開揉碎講清楚再講Manacher。整個過程我盡量用當初我學的時候踩過的坑的視角來寫配合完整的Java實現代碼最后附上刷題時常見的幾個問題排查思路。2. KMP算法next數組是靈魂2.1 從BF算法到KMP到底優(yōu)化了什么先明確一點KMP解決的是單模式串匹配問題。給定一個主串S和一個模式串P要在S中找到P第一次出現的位置。最原始的做法叫BF算法Brute Force也叫樸素匹配。BF的做法從S的每個位置i出發(fā)拿P逐位對齊比較。如果某一位失配就把P整體右移一位從P的第0位重新開始比較。public static int bfSearch(String s, String p) { int n s.length(), m p.length(); for (int i 0; i m n; i) { int j 0; while (j m s.charAt(i j) p.charAt(j)) { j; } if (j m) { return i; } } return -1; }這段代碼邏輯沒錯問題出在效率上。假設S是aaaaaaaaaaaaaaaaabP是aaab每次都要比較到P的最后一位才發(fā)現失配然后i只前進一位。整體下來近似比較nm次復雜度O(nm)。仔細想想BF到底浪費了什么信息答案是已經匹配成功的那一段被白白丟掉了。舉個例子SababcabcabababdPababd。當P的前4位abab都匹配成功第5位P[4]d與主串中的c失配時我們能從這個4位已經匹配的事實中推導出什么P的前綴abab有長度為2的公共前后綴ab這意味著如果把P右移2位P的前綴ab依然能和主串當前位置之前的ab對上。這個結論只需要分析P自己就能得到不需要知道主串的任何額外信息。KMP的核心思想就用一句話概括失配時利用模式串自身的結構信息把模式串一次性右移到可能匹配的最遠位置主串指針絕不回退。這里的模式串自身的結構信息就是next數組。2.2 next數組的兩種定義方式別再混了網上講KMP的教程next數組的定義有無數種版本本質都是最長公共前后綴長度但在具體實現上差一位。先明確一個基礎概念對于一個字符串它的前綴是去掉末尾若干字符后得到的子串后綴是去掉開頭若干字符后得到的子串。所謂最長公共前后綴就是既是前綴又是后綴的最長子串長度且這個子串不能是字符串本身也不能是空串。比如ababa長度為1的前后綴a和a相等匹配長度為1長度為2的前后綴ab和ba不等長度為3的前后綴aba和aba相等匹配長度為3長度為4的前后綴abab和baba不等所以ababa的最長公共前后綴長度是3。網上常見的next數組定義有兩種定義Anext[i]表示模式串P的[0, i)子串即P[0..i-1]的最長公共前后綴長度也就是中文教程里常說的前綴函數。這里的next[0]-1有些約定為0表示空串沒有公共前后綴。定義Bnext[i]表示模式串P的[0, i]子串即P[0..i]的最長公共前后綴長度即next[i]對應的是包含第i個字符在內的子串。兩種定義各有擁護者計算出來的next數組整體錯一位但匹配時的跳轉邏輯也相應調整。KMP本身沒有歧義算法是正確的歧義全在next數組的具體約定上。這篇文章里我采用題目中給出的定義來規(guī)定next[i]定義為模式串p[0..i-1]的最長公共前后綴長度不過next[0]我習慣設為-1用-1作為公共前后綴不存在的哨兵。為了避免歧義下面直接用具體例子說明。2.3 手算abacaba的next數組看題目里的例子模式串Pabacaba按照next[i]定義為p[0..i-1]的最長公共前后綴長度來計算。先拆開看每個前綴子串i0: 空串next[0] -1 i1: p[0]a最長公共前后綴長度為0next[1] 0 i2: p[0..1]ab前綴a后綴b不等next[2] 0 i3: p[0..2]aba前綴a后綴a長度1更長的不行next[3] 1 i4: p[0..3]abaca和c不等next[4] 0 i5: p[0..4]abaca前綴a后綴a長度1前綴ab和后綴ca不等next[5] 1 i6: p[0..5]abacab前綴ab后綴ab長度2aba和cab不等next[6] 2 i7: p[0..6]abacaba前綴aba后綴aba長度3next[7] 3所以得到i01234567next[i]-10010123這里的next[7]是最后用到的值嗎不一定。如果匹配到P最后一位失敗了需要跳轉到next[7]3也就是說明前7位都匹配上了但第8位失配此時模式串最長公共前后綴長度為3所以從下標3繼續(xù)嘗試。理解這個表之后再來看代碼實現。求next數組的代碼經典寫法如下public static int[] getNext(String p) { int m p.length(); int[] next new int[m 1]; next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p.charAt(i) p.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; }這段代碼的核心邏輯是用兩個指針i和jj代表已經匹配上的公共前后綴長度。如果p[i]p[j]說明公共前后綴可以延長一位繼續(xù)如果失配j就回退到next[j]相當于在計算next數組的過程中也要用到next數組自身的跳轉信息這就是遞歸地利用已計算的信息。有個細節(jié)值得注意next數組長度是m1而不是m因為按照定義Anext[m]是完整的P[0..m-1]的最長公共前后綴長度匹配過程中模式串走到頭時也要查這個值。2.4 KMP匹配過程主串指針不回退有了next數組匹配邏輯就順理成章了。public static int kmpSearch(String s, String p) { int n s.length(), m p.length(); if (m 0) return 0; int[] next getNext(p); int i 0, j 0; while (i n) { if (j -1 || s.charAt(i) p.charAt(j)) { i; j; } else { j next[j]; } if (j m) { return i - m; } } return -1; }匹配時最關鍵的跳轉分支是else當s[i] ! p[j]時主串下標i不動只把模式串下標j更新為next[j]。這里next[j]的含義是前j個字符已經匹配相同時最長公共前后綴的長度所以模式串跳到該長度處繼續(xù)比較而主串當前位置之前的那些字符已經保證與模式串前綴對齊了。用生活類比理解你在書里查找一個詞當連續(xù)幾頁都符合關鍵詞前綴突然某一頁對不上時你不會回到書的第一頁重查而是根據已經匹配到的部分把關鍵詞的某個前綴對齊到當前頁繼續(xù)往后翻。主串就好比書頁只有前進沒有后退模式串的移動靠next數組來指導。來看一個具體的匹配例子。主串Sababacabacaba模式串Pabacaba。i0j0s[0]a與p[0]a匹配i1j1i1j1s[1]b與p[1]b匹配i2j2i2j2s[2]a與p[2]a匹配i3j3i3j3s[3]b與p[3]c失配j跳到next[3]1主串不前進i3j1s[3]b與p[1]b匹配i4j2i4j2s[4]a與p[2]a匹配i5j3i5j3s[5]c與p[3]c匹配i6j4i6j4s[6]a與p[4]a匹配i7j5i7j5s[7]b與p[5]b匹配i8j6i8j6s[8]a與p[6]a匹配i9j7jm返回i-m2主串從位置2開始匹配成功即子串abacaba出現在S[2..8]位置。注意在第4步主串index3處的失配i沒有回退到1而是原地等待模式串通過next跳轉后繼續(xù)比較。這就是KMP主串不回退的直觀體現。KMP的時間復雜度為什么是O(nm)匹配過程中i只會增加不會減少最多增加n次j每次失配時通過next跳轉會變小但j增加的次數不超過i增加的次數每次匹配成功j加1匹配失敗j減少但總量有限整體均攤下來代價是線性的。求next數組同理i和j的移動次數也是O(m)。所以最終是O(nm)。2.5 KMP的應用遠不止字符串匹配很多初學者覺得KMP只能用來做文本里的子串查找其實它的應用面比想象中寬。第一個實用場景是判斷一個字符串是否是另一個字符串的循環(huán)移位。比如判斷B是否是A的循環(huán)移位常規(guī)思路是AA拼起來看B在AA中是否出現。這本質就是一次KMP匹配。第二個場景是求字符串的最短重復周期。給一個字符串s如果它可以由某個子串重復k次構成找出這個最小周期子串。結論是用KMP求出next數組后答案是n - next[n]如果n % (n - next[n]) 0那么這個最短重復周期長度就是n - next[n]。這個結論在很多字符串題里是隱藏考點。第三個場景是KMP自動機思想。把KMP的匹配過程理解成模式串在不同狀態(tài)之間跳轉這就是有限狀態(tài)自動機的雛形。AC自動機多模式串匹配、最大長度前綴匹配等進階算法都建立在這個思想上。所以說KMP不是孤立的一個小技巧它是很多字符串數據結構的底層地基。提示刷題時如果遇到判斷子串是否出現求最短周期循環(huán)移位這類描述第一反應應該是KMP或KMP的變形而不是直接上暴力。3. Manacher算法最長回文子串的線性解法3.1 回文問題的暴力解法為什么慢KMP講清楚了來看Manacher。這個算法解決的是最長回文子串問題比如給定字符串babad最長回文子串是bab或aba長度3。暴力解法有兩種思路。第一種是枚舉所有子串逐個判斷是否回文復雜度O(n3)基本屬于不可用。第二種是中心擴展法枚舉每個位置作為回文中心向兩邊擴展直到不能擴展為止記錄最長的回文長度。public static String longestPalindrome(String s) { if (s null || s.length() 1) return ; int start 0, maxLen 1; for (int i 0; i s.length(); i) { int len1 expand(s, i, i); // 奇數長度回文 int len2 expand(s, i, i 1); // 偶數長度回文 int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private static int expand(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }中心擴展法的時間復雜度是O(n2)在字符串長度幾百萬級別時完全跑不動。Manacher算法的目標是把復雜度壓到O(n)。它的核心優(yōu)化只有一條當我們要計算某個位置的回文半徑時如果這個位置位于之前某個大回文的內部那么可以利用回文的對稱性直接借用對稱位置的已知回文半徑作為初始值省去從1開始擴展的過程。3.2 鏡像對稱Manacher最巧妙的優(yōu)化要理解Manacher先弄明白四個變量C當前已知的回文串的中心位置R當前已知的回文串的最右邊界R右邊那個位置表示半徑覆蓋到R-1P[i]以位置i為中心的回文半徑包含中心本身mirror 2*C - ii關于C的對稱位置算法的核心邏輯是如果i在R的范圍內即i R那么P[i]至少等于min(P[mirror], R - i)。為什么因為i和mirror關于C對稱而C的回文范圍[R的左邊界, R]是對稱的。既然以C為中心的回文包含了i和mirror那么mirror回文半徑里的內容在i的鏡像位置上一定也是對稱的。所以P[i]可以直接從P[mirror]繼承這是Manacher的加速核心。但有個限制條件P[i]不能超過R-i因為一旦超過R就超出了C的回文覆蓋范圍這個范圍之外的對稱性就無法保證了。所以取min(P[mirror], R - i)。如果i在R之外沒有對稱信息可用P[i]初始為1。這里有一個關鍵問題回文半徑的奇偶性怎么處理回文串有兩種情況奇數長度如aba中心是單個字符b偶數長度如abba中心在bb之間。直接處理時需要區(qū)分兩種情況代碼寫起來麻煩而且P數組在不同情況下含義不一致。Manacher的經典做法是在原始字符串的每個字符之間包括首尾插入一個特殊字符比如把aba改寫成#a#b#a#把abba改寫成#a#b#b#a#。插入后原來的奇數回文和偶數回文都統一成了奇數回文以特殊字符為中心或普通字符為中心處理起來就不需要分支判斷了。這里的特殊字符可以是任何不沖突的字符比如#因為它不會與原始字符匹配。原始字符串s長度為n變換后的字符串t長度為2n1。求得的P[i]是t中以i為中心的回文半徑對應到原始字符串的回文長度就是P[i]-1。最終答案就是所有P[i]中的最大值減1。3.3 Manacher的完整實現與邊界分析直接看代碼public static String manacher(String s) { if (s null || s.length() 0) return ; // 構造帶分隔符的字符串 char[] chars new char[s.length() * 2 1]; int idx 0; for (int i 0; i chars.length; i) { chars[i] (i % 2 0) ? # : s.charAt(idx); } int n chars.length; int[] p new int[n]; int C 0, R 0; int maxLen 0, maxCenter 0; for (int i 0; i n; i) { // 利用對稱性初始化 p[i] if (i R) { int mirror 2 * C - i; p[i] Math.min(p[mirror], R - i); } else { p[i] 1; } // 中心擴展 while (i - p[i] 0 i p[i] n chars[i - p[i]] chars[i p[i]]) { p[i]; } // 更新 C 和 R if (i p[i] R) { C i; R i p[i]; } // 記錄最大長度 if (p[i] - 1 maxLen) { maxLen p[i] - 1; maxCenter i; } } // 根據中心位置還原原始字符串 int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen); }逐行拆解第一步構造帶分隔符的數組。偶數位放#奇數位放原始字符注意chars[1]是s[0]chars[3]是s[1]以此類推。第二步初始化P[i]。當i R時用對稱性預填一個初始值這樣while循環(huán)的擴展次數被大大壓縮。當i R時沒有對稱信息可用初始為1。第三步中心擴展。這個while循環(huán)看起來和暴力中心擴展一樣但它的執(zhí)行次數已經被前面的初始化大幅削減。注意邊界條件i - p[i] 0 和 i p[i] n防止數組越界。第四步更新C和R。C和R的更新原則是一旦發(fā)現當前位置的最右邊界超過了原來的R就更新R和C。這保證了后續(xù)位置盡量多的i能夠落在R的范圍內從而利用鏡像優(yōu)化。第五步記錄最大長度。maxLen p[i] - 1對應原始字符串的回文長度。還原原始字符串的下標時有一個小技巧maxCenter是變換后數組中的中心下標maxLen是原始回文長度那么原始字符串起始位置是(maxCenter - maxLen) / 2。這個公式可以自己推一下變換后的字符到原始字符的下標映射關系是rawIndex transformedIndex / 2因為插入字符占了一半位置回文在變換后數組中的區(qū)間是[maxCenter - maxLen, maxCenter maxLen]除2后對應的原始區(qū)間起點就是(maxCenter - maxLen) / 2。3.4 復雜度分析和幾個容易踩的坑Manacher的復雜度為什么是O(n)看似while循環(huán)里有一層嵌套但是注意每次while擴展都會使R向右移動而R在整個算法過程中只會向右移動最多移動n次。所以while循環(huán)的總執(zhí)行次數是O(n)的。P數組的初始化、C和R的更新都是O(1)操作總的循環(huán)次數n次所以整體是O(n)。實際操作中有幾個坑我在這里集中說一下第一個坑是分隔符的選擇。用#是慣例但要求這個字符不能出現在原始字符串里否則會干擾匹配。比如原始字符串里有#你還用#做分隔符整個算法的正確性就被破壞了。穩(wěn)妥做法是選一個不影響判斷的字符或者明確知道原始字符集范圍。第二個坑是P[i]的初始值。我見過很多人把p[i]初始化寫成0然后while循環(huán)里從i開始擴展這樣就會漏掉單個字符的回文情況導致邊界問題。記住p[i]至少是1因為單個字符本身是回文。第三個坑是還原原始字符串下標時容易算錯。直接用原始思路推導會快很多別死記公式推一遍就懂。第四個坑是C和R的更新時機。只有當i p[i] R時才更新等于不更新。因為等于的時候新的回文半徑沒有超出已有覆蓋范圍不需要調整。注意Manacher求的是最長回文子串的長度或者具體子串。如果題目只需要長度可以精簡掉字符串還原部分只保留maxLen的計算。Manacher在高頻面試題中的出現率很高尤其是字節(jié)、快手的算法題庫里最長回文子串幾乎是標配題用Manacher寫成O(n)級別面試官的印象分會比O(n2)高不少。4. bfprt算法確定性搞定TopK問題4.1 TopK問題為什么難在最壞情況前兩個算法都講完了最后說bfprt。整體安排在下一篇展開但核心思路和代碼框架值得先在這里鋪墊一下方便大家把三個算法串起來理解。問題定義給定一個無序數組找出第K小或第K大的元素。比如[3, 2, 1, 5, 6, 4]K2時答案是2排序后為[1,2,3,4,5,6]第2小是2。最簡單的做法是排序后取第K個復雜度O(n log n)。但這個問題比排序更簡單不需要完全有序所以期望做到O(n)。常見的優(yōu)化方案是快速選擇QuickSelect利用快速排序的partition思想每次選取一個pivot把數組分成小于pivot和大于pivot兩部分。如果pivot的位置恰好是K直接返回否則在左半邊或右半邊遞歸。隨機選pivot時期望復雜度是O(n)但最壞情況下每次選到最大或最小元素遞歸規(guī)模每次只減少1復雜度退化為O(n2)。bfprt算法要解決的就是這個最壞情況它通過一種確定性的pivot選擇策略保證無論輸入數據長什么樣復雜度都能控制在O(n)。4.2 中位數的中位數五個一組的原因bfprt的核心是中位數的中位數選主元思路整個過程分五步將數組按每5個元素一組分組最后一組不足5個也單獨成組對每組內的元素排序組內最多5個用插入排序即可取出每組的中位數放到一個新的數組中遞歸調用bfprt求這個中位數數組的中位數把它作為pivot用pivot對原數組做partition根據partition后的位置判斷是在左邊找還是在右邊找遞歸處理為什么必須是5個一組這是bfprt算法中最核心的證明點。假設數組有n個元素5個一組共有n/5組近似。每組內部排序后取中位數由于每組有5個元素中位數是第3個即每組有2個元素小于等于該組中位數2個元素大于等于。這些中位數的中位數記為pivot。那么有多少元素能確定小于pivot有一半的組的中位數小于等于pivot因為pivot是中位數的中位數這些組各有2個元素小于等于該組中位數所以這些組的至少3個元素小于等于pivot該組中位數本身加上2個更小的。粗略估算有約(n/10)*3 3n/10個元素一定小于pivot。同理約3n/10個元素一定大于pivot。所以partition之后最壞情況下遞歸處理的子問題規(guī)模不超過7n/10。由此得到遞歸式T(n) ≤ T(n/5) T(7n/10) O(n)其中T(n/5)是求中位數的中位數的時間T(7n/10)是遞歸查找的時間O(n)是分組、排序、partition的時間。解這個遞歸式最終得到T(n) O(n)。用替代法可以直接證明。為什么不用3個一組3個一組的話每組中位數以上的元素有2個有一半組的中位數小于pivot所以能確定小于pivot的元素約(n/6)*2 n/3遞歸規(guī)模變?yōu)?n/3遞歸式變?yōu)門(n) ≤ T(n/3) T(2n/3) O(n)這個式子解出來是O(n log n)無法保證線性。7個一組可以但分組排序的常數更大實際運行更慢。5個一組是數學證明和工程效率的平衡點。4.3 bfprt的確定性為什么重要bfprt相對QuickSelect的優(yōu)勢是確定性。QuickSelect依賴隨機性雖然期望復雜度是O(n)但在某些特定輸入下比如數組已經有序且每次pivot都選到最小值會退化。bfprt不依賴數據分布無論輸入什么都能保證O(n)。但是這里要說不中聽的話bfprt的常數特別大每次遞歸都要分組、組內排序、求中位數數組的中位數實際運行時間可能比QuickSelect慢好幾倍。所以它在工程中很少直接使用更多是作為理論工具出現。比如在算法課上證明選擇問題存在確定性線性算法或者在某些實時系統里要求最壞情況可控的場景。面試中如果被問到建議這樣回答先說bfprt是確定性O(n)的TopK算法再說五步流程最后強調5個一組的原因——保證每次partition至少刪除3n/10個元素遞歸規(guī)模最多7n/10最終解出O(n)。完整代碼實現、變種問題和復雜度的嚴格數學證明我放在下一篇寫。這里先給出一個簡單的Java框架方便對照理解public static int bfprt(int[] arr, int k) { // k從1開始計數 return bfprt(arr, 0, arr.length - 1, k - 1); } private static int bfprt(int[] arr, int left, int right, int k) { if (left right) return arr[left]; int pivot medianOfMedians(arr, left, right); int[] range partition(arr, left, right, pivot); if (k range[0] k range[1]) { return arr[k]; } else if (k range[0]) { return bfprt(arr, left, range[0] - 1, k); } else { return bfprt(arr, range[1] 1, right, k); } }這里的medianOfMedians對應上面說的選主元邏輯partition是荷蘭國旗問題的三路快排寫法。等下篇再展開。5. 常見問題與排查技巧實錄5.1 KMP next數組求錯的排查思路KMP寫出來跑一遍結果不對90%的情況是next數組求錯了。排查時按以下步驟走第一步對照你采用的next定義手算幾個簡單串的結果比如aaaa、abab、abcabc看看你的代碼輸出是什么。如果手算和代碼不一致說明理解或實現有一方出了問題。第二步重點檢查求next的循環(huán)邊界。while循環(huán)的終止條件、i和j的初始值、next[i]賦值時機這三處最容易錯。比如忘了next[0]-1或者在失配時回退j寫成j--而不是jnext[j]都會導致結果偏差。第三步打印匹配過程的中間變量。在kmpSearch的else分支里打印i和j的值觀察主串指針是否真的沒有回退模式串跳轉是否和手算一致。我見過一個典型錯誤定義A和定義B混用。求next時用定義Anext[i]p[0..i-1]的最長公共前后綴但匹配跳轉時卻按定義B的邏輯來。雖然只是差一位但最終的匹配結果完全不對。5.2 Manacher邊界問題排查Manacher代碼不長但邊界問題非常隱蔽。如果你發(fā)現結果差一位或者偶數字符串處理錯先檢查以下幾點第一檢查構造的變換數組是否正確。下標0放#下標1放s[0]下標3放s[1]這個映射錯了整個算法全崩?？梢韵却蛴∽儞Q后的字符數組肉眼核對。第二檢查while循環(huán)的邊界條件。i - p[i] 0和i p[i] n這兩個條件缺一不可少寫一個就會數組越界。第三檢查還原回文子串的公式。之前提到start (maxCenter - maxLen) / 2這里maxCenter是變換后數組的下標maxLen是原始回文長度。如果你用p[i]直接當作原始長度還原出的字符串就是錯的。第四檢查空串和單字符的邊界情況?？沾苯臃祷乜諉巫址祷刈陨磉@兩個case要單獨處理。5.3 面試中的常見追問與應對思路這三個算法在面試中只會寫代碼是不夠的很可能被追問到原理層面的問題。對于KMP面試官最常問的是next數組怎么來的為什么時間復雜度是O(n)next[j]回退時為什么不會漏掉可能的匹配回答時抓住主串指針不回退和利用模式串自身的最長公共前后綴信息這兩個核心就行。對于Manacher高頻追問是為什么插入分隔符后能統一奇偶為什么P[i]的初始值取min(P[mirror], R-i)復雜度的直觀解釋是什么回答時記得強調超過R的部分對稱性無法保證所以必須取min這個關鍵點。對于bfprt高頻追問是為什么是5個一組3個一組行不行怎么證明復雜度是O(n)回答時把遞歸式和分組淘汰比例講清楚基本就能過。還有一個小技巧面試時如果寫了bfprt可以先說一句這個算法常數比較大實際工程中通常用隨機化QuickSelect但bfprt的優(yōu)勢是確定性O(n)。這句話能體現你對算法有整體認知而不僅僅是背了模板。6. 三個算法的共同主線把KMP、Manacher、bfprt放一起講完再回頭看它們的聯系。KMP的next數組是利用已匹配部分的公共前后綴信息避免主串回退Manacher的P數組是利用回文的鏡像對稱性避免重復擴展bfprt是分組取中位數再取中位數的中位數避免partition選到極端pivot。三個算法從不同的角度驗證了同一個道理算法優(yōu)化的本質是信息的最大化復用以及最壞情況的主動規(guī)避。這個道理應用到實際開發(fā)中很多性能問題都能找到優(yōu)化思路。比如處理字符串時如果發(fā)現某些子串被反復計算就要考慮預處理記憶化處理大數據時如果某種選主元策略在極端輸入下會退化就要考慮更穩(wěn)妥的確定性策略。下一篇會展開bfprt的完整實現包括每組排序代碼、中位數數組的遞歸處理、partition的三路劃分以及幾個變種題目第K大、找中位數、找出所有TopK元素的解法。到時候拿到代碼建議先自己跑一遍再試著改一改比單純看一遍印象深得多。我自己帶過的學員里很多人卡在這三個算法上是因為眼高手低——看講解都覺得懂了一寫代碼就各種邊界問題。所以這里多說一句算法這東西看一百遍不如手寫五遍寫完再對著測試用例跑尤其要把剛才說的邊界情況全部測一遍。這個過程不是浪費時間而是真正把別人的解法變成自己的內功。