Manacher最長回文
利用已知回文的對稱性省掉重複展開。
用在：DNA 回文片段、文字分析
01為什麼需要它
分子生物學實驗要知道一段 5 萬鹼基的質體上，哪些位置會被限制酶切開。很多限制酶辨識的序列是「反向互補等於自己」的片段，例如 EcoRI 的 GAATTC，反過來讀再把 A、T 與 C、G 互換，還是 GAATTC。
為什麼用它把回文的「對稱位置相等」換成「對稱位置互補」，Manacher 的鏡像論證一樣成立，因為互補關係對調兩次會回到原本的字母；唯一要多加的規定是中心必須落在兩個鹼基之間，因為沒有鹼基和自己互補。一次 O(n) 就得到每個中心能延伸多遠，所有長度至少 6 的互補回文一起列出，再和限制酶的辨識序列表對照。
研究者觀察到疱疹病毒的基因組裡，有些區域的回文序列特別密集，而這些區域常常就在 DNA 複製起點附近。要在 20 多萬鹼基的基因組上，用滑動區間統計每一段裡回文的數量，找出異常密集的地方。
為什麼用它Manacher 算出每個中心的最長回文半徑之後，以同一個中心、較短的回文全部都成立，所以每個中心的回文數量直接由半徑算出，不必逐一展開。整條基因組 O(n) 處理完，再用前綴和就能 O(1) 查詢任意區間內的回文數量。
把一個長 2,000 的字串切成最少段回文，動態規劃枚舉切點時要問上百萬次「s[l..r] 是不是回文」；另一類題目則是字串長 10 萬、查詢 10 萬次。每次都從兩端往中間比，最壞 O(n) 一次。
為什麼用它s[l..r] 在插入分隔字元後的中心是 l + r + 1，它是回文當且僅當那個中心的半徑至少是 r − l + 1。Manacher 預處理 O(n) 之後，每次查詢 O(1)，也不需要 O(n²) 的回文表。
看到這些關鍵字就想到它：最長回文子字串、回文子字串的數量、以每個位置為中心能延伸多遠、大量區間回文查詢、DNA 反向互補片段、需要比 O(n²) 中心展開更快。
02核心概念
找最長回文子字串最直接的做法是中心展開：以每個字元、以及每兩個字元之間為中心往外擴，直到兩邊不同。遇到 aaaa…a 時每個中心都擴到底，最壞 O(n²)。奇數長度的回文中心在字元上、偶數長度的在字元之間，分開處理很麻煩，所以先在每個字元之間和頭尾插入分隔字元：s = abaaba 變成 T = #a#b#a#a#b#a#，長度 2n + 1，所有回文的中心都落在 T 的某個位置上。p[i] 是 T 上以 i 為中心的回文半徑，巧的是它剛好等於對應回文在 s 裡的長度，起點是 (i − p[i]) / 2。
Manacher 維護右界最遠的回文：中心 c、右界 r = c + p[c]。處理 i 時如果 i < r，i 在這個大回文裡，它關於 c 的鏡像 j = 2c − i 已經算過。大回文左右對稱，i 附近的字元就是 j 附近字元的鏡像。若 p[j] < r − i，j 的回文連同讓它停下來的那個字元都在大回文裡，i 會在同樣的地方停下，直接 p[i] = p[j]，一次比較都不用。若 p[j] ≥ r − i，只能保證半徑至少 r − i，右界外面的字元沒看過，要從那裡繼續往外比。若 i 在右界之外，就從半徑 0 開始展開。每次展開完，如果 i + p[i] > r，就把中心和右界換成 i。
複雜度：從 min(p[j], r − i) 開始往外比時，每一次成功的比較都會把右界往右推一格，r 只增不減、最多到 2n + 1，所以成功的比較總共是 O(n)；失敗的比較每個 i 最多一次。整體 O(n) 時間、O(n) 空間。一次算出的 p 陣列可以回答很多問題：最大的 p[i] 是最長回文；以 i 為中心的回文有 ⌈p[i] / 2⌉ 個，加總就是回文子字串的總數；s[l..r] 是回文當且僅當 p[l + r + 1] ≥ r − l + 1。
常見的坑：沒插分隔字元就只找得到奇數長度的回文，abba 會被漏掉；T 和 s 之間的位置換算差一，起點要用 (i − p[i]) / 2；抄鏡像半徑時忘了和 r − i 取最小值，會把右界外沒看過的字元也當成對稱；展開時沒有檢查兩端邊界。p[j] 嚴格大於 r − i 時其實答案就是 r − i，不過統一寫成繼續往外比，也只是多一次失敗的比較。和鄰近課程的關係：這和上一篇 Z-Algorithm 是同一個套路，「在伸得最遠的區間裡借鏡像位置的答案，只有超出區間才自己比」；用字串雜湊加二分半徑也能做到 O(n log n)；區間 DP 的回文表是 O(n²)，Manacher 在只需要回文資訊時可以取代它。
03演算法步驟
- 1在 s 的每個字元之間和頭尾插入分隔字元，得到長度
2n + 1的 T；p 陣列全部設 0，c = r = 0。 - 2對每個 i：若
i < r，令p[i] = min(p[2c − i], r − i)；否則p[i] = 0。 - 3在兩端都沒有越界、而且
T[i − p[i] − 1] = T[i + p[i] + 1]時，p[i] 加 1。 - 4若
i + p[i] > r，令c = i、r = i + p[i]。 - 5讀答案：最大的
p[i]是最長回文長度，在 s 中從(i − p[i]) / 2開始；s[l..r]是回文當且僅當p[l + r + 1] ≥ r − l + 1。
04互動示範
s = abaaba 插入 # 之後是 T = #a#b#a#a#b#a#，長度 13。第一列的藍色是 i，綠色是它相對於目前中心的鏡像 2c − i，黃色是以 i 為中心展開出的回文；第二列標出右界最遠的回文。i = 1 和 3 都在右界外，老實展開，i = 3 以 b 為中心得到半徑 3，也就是 aba，右界推到 6。i = 4 的鏡像是 2，p[2] = 0 比到右界的 2 格小，直接抄 0。i = 6 是 aa 中間的 #，鏡像 p[0] = 0 等於到右界的 0 格，只能自己展開，一路擴到 T 的兩端，半徑 6，右界推到 12。之後 i = 7、8、10 全部抄鏡像；i = 9、11、12 的鏡像半徑剛好等於到右界的距離，但右界已經是字串結尾，比一次就停。最大的 p 在 i = 6，對應 s 從 0 開始、長度 6 的 abaaba。
05程式碼
Python 用 None 當分隔字元，保證不會和任何字元相等，並示範最長回文、回文子字串計數，以及 O(1) 的區間回文查詢。C++ 把「兩個對稱位置算不算相符」抽成參數，同一份 Manacher 既能找一般回文，也能找 DNA 的互補回文；和自己不相符的位置不能當中心，這一行對一般回文沒有影響，對 DNA 則排除了以鹼基為中心的假回文。範例裡找出的兩個片段正是 EcoRI 和 BamHI 的切位。
def manacher(s):
"""在 t = #s[0]#s[1]#…# 上求回文半徑 p。p[i] 剛好等於對應回文在 s 裡的長度。O(n)"""
t = [None] * (2 * len(s) + 1)
t[1::2] = s # 奇數位置放字元，偶數位置是分隔（None 不會等於任何字元）
n = len(t)
p = [0] * n
c = r = 0 # 右界最遠的回文：中心 c，右界 r = c + p[c]
for i in range(n):
if i < r:
p[i] = min(p[2 * c - i], r - i) # 抄鏡像位置的半徑，但最多借到右界
while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
p[i] += 1 # 右界以外只能自己往外比
if i + p[i] > r:
c, r = i, i + p[i]
return p
def longest_palindrome(s):
p = manacher(s)
i = max(range(len(p)), key=p.__getitem__)
start = (i - p[i]) // 2 # t 的位置換回 s 的位置
return s[start:start + p[i]]
def count_palindromes(s):
"""回文子字串總數（位置不同就算不同）：每個中心貢獻 ceil(p / 2) 個"""
return sum((v + 1) // 2 for v in manacher(s))
class PalindromeQuery:
"""預處理 O(n)，之後每次問「s[l..r] 是不是回文」都是 O(1)"""
def __init__(self, s):
self.p = manacher(s)
def is_palindrome(self, l, r): # 閉區間 [l, r]，在 t 裡的中心是 l + r + 1
return self.p[l + r + 1] >= r - l + 1
if __name__ == "__main__":
print(manacher("abaaba")) # [0, 1, 0, 3, 0, 1, 6, 1, 0, 3, 0, 1, 0]
print(longest_palindrome("forgeeksskeegfor")) # geeksskeeg
print(count_palindromes("aaa"), count_palindromes("abaaba")) # 6 11
q = PalindromeQuery("abaaba")
print(q.is_palindrome(1, 4), q.is_palindrome(0, 3), q.is_palindrome(0, 2)) # True False True：baab、abaa、aba06練習題
- LeetCode 5Longest Palindromic SubstringMedium
- LeetCode 647Palindromic Substrings（每個中心貢獻 ⌈p / 2⌉ 個）Medium
- LeetCode 132Palindrome Partitioning II（DP 裡的回文判斷改成 O(1) 查詢）Hard
- LeetCode 2472Maximum Number of Non-overlapping Palindrome SubstringsHard
- LeetCode 1960Maximum Product of the Length of Two Palindromic Substrings（Manacher 加前後綴最大值）Hard
- LeetCode 3327Check if DFS Strings Are Palindromes（樹的走訪序列上跑 Manacher）Hard