在一堆字裡找「最長的回文」。插分隔符統一奇偶,靠鏡射把 O(n²) 壓成 O(n)。
aba、abba、上海自來水來自海上)。找一個字串裡最長的回文子串,暴力法要 O(n³)、中心擴展要 O(n²),而 Manacher 只要 O(n)。它靠兩個巧思:①在每個字元間插分隔符 #,讓奇數、偶數長度的回文統一成有正中心的奇數;②維護「目前最右邊的回文」,新位置若還在它範圍內,就直接抄鏡射位置算過的答案,不重複比較。
問題:奇偶要分開處理 —— aba(奇)的中心是字元 b;abba(偶)的中心卡在兩個 b 中間,沒有正中心。分兩種情況寫很麻煩。
解法:每個縫都插一個 # —— abba → #a#b#b#a#、aba → #a#b#a#。插完之後,任何回文長度都是奇數、都有一個正中心。
偶回文的中心變成 # —— abba 的中心落在正中間那個 # 上;奇回文的中心還是原字元。於是同一套程式就處理完兩種情況。
回文半徑 p[i] —— 對轉換後字串的每個位置 i,記「以它為中心、往外能對稱多遠」的半徑。max(p) 就是原字串最長回文的長度。
維護最右回文 (C, R) —— C 是目前「右界最靠右」的那個回文的中心、R 是它的右界。
在窗內就抄鏡射 —— 若 i < R,i 相對 C 的鏡射位置 i' = 2C − i 早就算過。由對稱性,p[i] 至少是 min(R − i, p[i']) —— 直接抄當起點,省下重複比較。
抄完再試著往外擴 —— 抄到的部分保證對稱;超過 R 的部分沒驗證過,才需要一格一格擴。因為每次擴都會把 R 往右推,整體只擴 O(n) 次。
n² 個)再逐一檢查是不是回文(n)。p。回文就是「以中心為鏡,左右完全對稱」。Manacher 就是沿著每個可能的鏡面,量它能對稱多寬。
大回文內部左右對稱,右邊某格的答案,跟它鏡射的左邊那格一樣 → 直接抄,不用重算。
在每個字縫插一塊 # 隔板,本來「卡在縫裡」的偶回文,就有了正中心,奇偶一視同仁。
對 abba 插分隔符成 #a#b#b#a#,逐位置算回文半徑 p(格子下方數字)。紫色是目前中心 i、琥珀是它的鏡射位置、淺綠是目前對稱到的範圍。看位置 4 的 # 怎麼一舉擴到整個 abba,之後 5、6、7 又怎麼直接抄鏡射。按「下一步」。
#a#b#b#a#(下方數字 = 回文半徑 p):從 Manacher 完整版、中心擴展、暴力法,到分隔符轉換、鏡射核心、只求長度、數回文子串,再到三法對照與小結。
❌ 忘了處理奇偶兩種回文 —— 沒插分隔符的話,中心擴展要分開跑「單字元中心」和「兩字元之間」兩種;插了 # 就統一了。
❌ 換算回原字串位置算錯 —— 轉換後中心 c、半徑 m,原字串起點是 (c − m) // 2、長度是 m。這步很容易差一。
❌ 擴展時越界 —— while 條件要先檢查 i−p−1 ≥ 0 且 i+p+1 < n 再比字元,不然會索引越界。
❌ 為了 O(n) 硬上 Manacher —— 邊界多、容易寫錯。n 不大就用中心擴展 O(n²),又短又穩,面試也接受。
abba 轉換後 p 陣列長怎樣?最大值在哪個位置?對應原字串的最長回文是什麼?# 到底解決了什麼問題?為什麼插完之後,所有回文長度都變成奇數?把答案打到對話裡,我幫你對。