刷題(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-i2.當i3.當i=mx-i。其迴文半徑最短為mx-i4.當i>mx, i已經在mx的右邊,i為中心的迴文子串的半徑無法預測,其最小長度為1.也就是說,當i

算法代碼實現:

馬拉車算法

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

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

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