# Algorithm 演算法 - 最長回文子字串 馬拉車算法 Manacher's algorithm

# 簡介 Intro

以下取自維基百科

Manacher 於 1975 年發現了一種線性時間演算法，可以在列出給定字串中從任意位置開始的所有回文子串。並且，Apostolico, Breslauer & Galil 發現，同樣的演算法也可以在任意位置尋找全部極大回文子串，並且時間複雜度是線性的。因此，他們提供了一種時間複雜度為線性的最長回文子串解法。另外，Jeuring (1994), Gusfield (1997) 發現了基於字尾樹的演算法。也存在已知的高效並列演算法。

最長回文子串演算法(Longest palindromic substring)不應當與最長回文子序列演算法(Longest Palindromic Subsequence)混淆。

## 演算法講解

### 插入符號使其成奇數

首先因為我們要找出子字串，而其中最好且長度最長的情況下就是整個字串都是回文，而在計算長度的情況下，就會有長度是奇數和偶數的狀況。而為了方便我們去找出中心點來計算出半徑長度，我們從頭至尾在字符間都插入一個無意義的符號，所以目前有以下的假定。

-   字串：`S`
-   字串長度：`L`
-   插入符號 `#` 在 `S` 從頭至尾的字符中間(包含頭跟尾)

為什麼要插入符號，就可以方便我們找出中心點呢？因為 2L + 1 會是奇數，什麼意思呢？我們可以有兩種狀況，`L` 是奇數跟偶數的狀況。

```python
# 奇數
S: str = "aba"
print(len(S))    # 3
# S 轉換後
S: str = "#a#b#a#"
print(len(S))    # 7 = 2 * 3 + 1

# 偶數
S: str = "abba"
print(len(S))  # 4
# S 轉換後
S: str = "#a#b#b#a#"
print(len(S))  # 9 = 2 * 4 + 1
```

發現到了嗎？今天不管是奇數還是偶數，只要乘上 2 再加上 1 就一定都會是奇數，而只要是奇數就一定會有一個平均長度的中心點，這可以方便我們做拆半處理。

### 邏輯前提

我們將先計算出最終形態的樣子，以下分別是奇數和偶數的情況在演算法最後的型態。假設在該位置的最長回文字串長度是 `LPS`

**偶數：**`S = "abaaba"`

|          | #   | a   | #   | b   | #   | a   | #   | a   | #   | b   | #   | a   | #   |
| -------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| index    | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  | 12  |
| LPS 長度 | 0   | 1   | 0   | 3   | 0   | 1   | 6   | 1   | 0   | 3   | 0   | 1   | 0   |

**奇數：**`S = "abababa"`

|          | #   | a   | #   | b   | #   | a   | #   | b   | #   | a   | #   | b   | #   | a   | #   |
| -------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| index    | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  | 12  | 13  | 14  |
| LPS 長度 | 0   | 1   | 0   | 3   | 0   | 5   | 0   | 7   | 0   | 5   | 0   | 3   | 0   | 1   | 0   |

會先發現以下三個特性：

1. 在 `index` 偶數的時候 `LPS >= 0`
2. 在 `index` 奇數的時候 `LPS >= 1`，因為至少兩側插入的符號會相等，所以至少有 1。
3. 在對稱點右半，其右邊界的 `index` 與字母的 `index` 相減就會等於 LPS 長度。 `index 14 - index 9 = LPS[9]`

接下來的目標就是找出所有位置的 LPS，然後比較出最大值。

### 快速找出每個位置的 LPS

要最快的找出每個位置的 LPS，就要好好的利用回文的特性了，也是 Manacher 演算法的整個重點，什麼意思呢？

以上方偶數列表為範例，我們看看 `index = 3` 的位置：

-   index 2 跟 4 的 LPS 相同
-   index 1 跟 5 的 LPS 相同

我們從左到右來計算 LPS，所以當我們已經知道 index 1, 2, 3 的 LPS 時，因為回文特性。4 和 5 都在 3 的回文半徑內，所以我們就可以知道 4 和 5 的 LPS 保底值(這邊要注意說的是保底值喔)。

換成奇數的範例來看，在 index 3 和 11，雖然 LPS 是 3，但是在其半徑內其他位置的 LPS 卻是 3 跟 5，你可以發現這不是對稱的。所以才說是保底值，就至少會有 1 但是可以更多。

而 Manacher 演算法就是利用這個回文的特性減少計算 LPS 來達到線性的複雜度。總共會有以下三種情境，各個情境就會推導出不同的條件，來幫助我們判斷。

以下我們先定義變數，方便在下面的情境上討論：

-   `LPS`：儲存以各位置為中心的最大回文長度
    `LPS[4]` 就是以 index 4 為中心的最大回文長度是多少
-   `border_right`：大回文的右邊界位置
-   `current`：目前的位置
-   `mirror`：`current` 對稱的位置

#### 情境ㄧ：對稱回文在大回文字串邊界內

例如 d**_aca_**x**_aca_**d 其中 `aca` 在 `dacax` 中，沒有超出左邊界。在回文對稱的特性下右側也不會超出範圍。這種情況下就可以轉化成以下的條件。

```python
LPS[current] == LPS[mirror]
LPS[current] == min(LPS[mirror], border_right - current) # 保底值，所以取最小的
```

#### 情境二：左側對稱回文剛好貼在大回文左邊界上

```text
|xxxx|      |xxxx|?
|--------x-------|
```

這個情境跟情境一，最大的差別在於，因為你無法確定右側邊界是不是也到底了，如果沒有到底那就有可能會在擴大。所以最後的條件會是。

```python
LPS[current] == LPS[mirror]
LPS[current] >= min(LPS[mirror], border_right - current) # 保底值，所以取最小的。而且因為還有可能擴展，所以跟情境一不同的是 >=
```

#### 情境三：左側對稱回文超出大回文左邊界

```text
|xxxx|           |xx|?
   |--------x-------|
```

例如 **_dcbabcd_**xd**_cbabc_**e，其中左側 `dcbabcd` 超出了大回文 `cbabcdxdcbabc` 的左邊界。這邊是因為範例，所以我們之後右側已經無法再繼續擴展了。但實際情況是有可能在擴展，所以跟情境二一樣的條件。

```python
LPS[current] == LPS[mirror]
LPS[current] >= min(LPS[mirror], border_right - current) # 保底值，所以取最小的。而且因為還有可能擴展，所以跟情境一不同的是 >=
```

### 總結

所以總結來說三種情境我們只需要考慮當大回文的左邊界被觸碰或超過時，就要試著往外擴展去判斷是不是還有發展空間。而一旦發現了更長的 `border_right` 就將其替換過去新的回文區間。

### 程式實作範例

```python
def longestPalindrome(self, s: str) -> str:
    expand_str: str = '#'.join(f'^{s}$')
    n: int = len(expand_str)
    LPS: list[int] = [0] * n
    center: int = 0
    right: int = 0

    for i in range(1, n - 1):
        i_mirror: int = 2 * center - i
        # Case 1 : 沒有超過右邊界
        if i < right:
            LPS[i] = min(LPS[i_mirror], right - i)

        # 剩下 Case 2, 3：右邊界需要往右擴展
        while expand_str[i + (LPS[i] + 1)] == expand_str[i - (LPS[i] + 1)]:
            LPS[i] += 1

        # 如果新字串回文超過現有回文右邊界，判斷是否需要更新右邊界
        if LPS[i] + i > right:
            center, right = i, LPS[i] + i

    # 找出 LPS 的最大值和其中心點
    max_len, center_idex = max((n, i) for i, n in enumerate(P))
    return s[(center_idex - max_len) // 2: (center_idex + max_len) // 2]
```

## Reference

-   [最長回文子串 - 維基百科](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2)
-   [5. Longest Palindromic Substring](https://zhuanlan.zhihu.com/p/55666886)
-   [LeetCode - Longest Palindromic Substring](https://josephjsf2.github.io/data/structure/and/algorithm/2020/10/10/manacher-algorithm.html)
-   [[演算法] Manacher’s Algorithm 筆記](https://medium.com/hoskiss-stand/manacher-299cf75db97e)