刷題(leetcode)中心擴展算法

今天又在刷題，其實我感覺題不在多，而是通過一道題來理解一種算法，今天我們以下面一道題開始：

給定一個字符串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: "babad"

輸出: "bab" 注意: "aba" 也是一個有效答案。

分析：

首先要理解什麼是迴文子串，迴文是一個正讀和反讀都相同的字符串，例如“aba” 是迴文，而 “abc” 不是。因此，迴文可以從它的中心展開，並且只有 2n−1 個這樣的中心。你可能會問，為什麼會是 2n −1 個，而不是 n箇中心？原因在於所含字母數為偶數的迴文的中心可以處於兩字母之間“bb”的中心在兩個 ‘bb’ 之間

中心擴展算法

我們觀察到迴文中心的兩側互為鏡像。因此，迴文可以從它的中心展開

中心擴展算法

馬拉車算法（Manacher）

1、調整字符串

迴文子串有兩種可能"aba"和"bb"，如果直接處理需要判斷子串中心是否有字符。而馬拉車算法先為字符串填充無效字符，例如"#"。這樣上述字符串就變成"#a#b#a#"和"#b#b#"。這樣無論原字符串怎樣，新生成的字符串都是長度為奇數，中心有字符

2、計算半徑數組 p

接下來，我們需要想辦法計算出一個數組 p，這個數組的長度與處理後的字符串 ss 等長，其中 p[i] 表示以 ss[i] 為中心的最長迴文子串的半徑（不包括 p[i] 本身），暫且把它成為半徑數組。如果 p[i] = 0，則說明迴文子串就是 ss[i] 本身。

比如 “#a#b#” 的半徑數組為 [0, 1, 0, 1, 0]。

為了在搜索迴文子串時避免總是判斷是否越界，我們在 ss 的首尾兩端加上兩個不同的特殊字符，保證這兩個特殊字符不會出現在 ss 中。比如為 $ 和 ^。則 ss 變為了

ss = "$#g#o#o#g#l#e#^"

數組 p 的最大半徑，就是我們要尋找的最長迴文子串的半徑。因此只要計算出了數組 p，最後答案就呼之欲出了。

如何計算數組 p

一般的方法，是以中心點為中心，挨個將半徑逐步擴張，直至字符串不再是迴文字符串。但是這樣做，整體的算法複雜度為 O(n2)O(n2)。馬拉車算法的關鍵之處，就在於巧妙的應用了迴文字符串的性質，來計算數組 p。

馬拉車算法在計算數組 p 的整個流程中，一直在更新兩個變量：

id：迴文子串的中心位置

mx：迴文子串的最後位置

使用這兩個變量，便可以用一次掃描來計算出整個數組 p，關鍵公式為：

p[i] = min(mx-i, p[2 * id - i])

我們用圖示來理解這個公式，如下圖：

當前，我們已經得到了 p[0…i-1]，想要計算出 p[i] 來。紅1為以 j 為中心的迴文子串，紅2為以 i 為中心的迴文子串，紅3為以 id 為中心的迴文子串（首尾兩端分別為mx的對稱點和mx）。

那麼，如果 mx 在 i 的右邊，則我們可以通過已經計算出的 p[j] 來計算 p[i]，其中 j 與 i 的中心點為 id。這裡分兩種情況：

先直接令 p[i] 的迴文子串就等於 p[j] 的迴文子串，即紅2長度等於紅1，然後判斷紅2的末尾是否超過了 mx，如果沒有超過，則說明 p[i] 就等於 p[j]。

為什麼呢？

因為以 id 為中心的迴文子串為紅3，包含了紅1和紅2，而且紅1和紅2以 id 為中心，那麼一定有紅2=紅1。並且已經知道，紅1是以 j 為中心的最長子串，那麼紅2也肯定是以 i 為中心的最長子串。

如果紅2的末尾超過了 mx，那麼就只能讓 p[i] = mx - i了，即我可以保證至少半徑到 mx 這個位置，是可以迴文的，但是一旦往右超出了 mx，就不能保證了，剩下的只能用笨方法慢慢擴張來得到最長迴文子串。

那如果紅2的左邊超出了mx的對稱點，怎麼辦？不會出現這種情況的，因為紅1的右邊不會超過mx。如果超過了mx，那麼在上一次迭代中，id應該更新為j，mx應該更新為 j+p[j]。在迭代中，會始終保證 mx 是所有已經得到的迴文子串末端最靠右的位置。

• 1.如果當前位置為i, 目前最觸及右邊的迴文子串的最右邊是mx、中心是id。則i的對稱點為: j = 2*id-i
• 2.當i
• 3.當i=mx-i。其迴文半徑最短為mx-i
• 4.當i>mx, i已經在mx的右邊，i為中心的迴文子串的半徑無法預測，其最小長度為1.
• 也就是說，當i

算法代碼實現：

馬拉車算法

這個算法理解其實確實花點精力，主要參考下面這篇文章，大家可以去看，致敬原作者

https://www.cnblogs.com/grandyang/p/4475985.html

同時題目來自於leetcode，本文主要是學習筆記，如有侵權聯繫刪除