Manacher

描述

給定一個長度為 \(n\) 的字符串 \(s\)，請找到所有對 \((i, j)\) 使得子串 \(s[i \dots j]\) 為一個迴文串。當 \(t = t_{\text{rev}}\) 時，字符串 \(t\) 是一個迴文串（\(t_{\text{rev}}\) 是 \(t\) 的反轉字符串）。

解釋

顯然在最壞情況下可能有 \(O(n^2)\) 個迴文串，因此似乎一眼看過去該問題並沒有線性算法。

但是關於迴文串的信息可用 一種更緊湊的方式 表達：對於每個位置 \(i = 0 \dots n - 1\)，我們找出值 \(d_1[i]\) 和 \(d_2[i]\)。二者分別表示以位置 \(i\) 為中心的長度為奇數和長度為偶數的迴文串個數。換個角度，二者也表示了以位置 \(i\) 為中心的最長迴文串的半徑長度（半徑長度 \(d_1[i]\)，\(d_2[i]\) 均為從位置 \(i\) 到迴文串最右端位置包含的字符個數）。

舉例來説，字符串 \(s = \mathtt{abababc}\) 以 \(s[3] = b\) 為中心有三個奇數長度的迴文串，最長迴文串半徑為 \(3\)，也即 \(d_1[3] = 3\)：

\[ a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c \]

字符串 \(s = \mathtt{cbaabd}\) 以 \(s[3] = a\) 為中心有兩個偶數長度的迴文串，最長迴文串半徑為 \(2\)，也即 \(d_2[3] = 2\)：

\[ c\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d \]

因此關鍵思路是，如果以某個位置 \(i\) 為中心，我們有一個長度為 \(l\) 的迴文串，那麼我們有以 \(i\) 為中心的長度為 \(l - 2\)，\(l - 4\)，等等的迴文串。所以 \(d_1[i]\) 和 \(d_2[i]\) 兩個數組已經足夠表示字符串中所有子迴文串的信息。

一個令人驚訝的事實是，存在一個複雜度為線性並且足夠簡單的算法計算上述兩個「迴文性質數組」\(d_1[]\) 和 \(d_2[]\)。在這篇文章中我們將詳細的描述該算法。

解法

總的來説，該問題具有多種解法：應用字符串哈希，該問題可在 \(O(n \log n)\) 時間內解決，而使用後綴數組和快速 LCA 該問題可在 \(O(n)\) 時間內解決。

但是這裏描述的算法 壓倒性 的簡單，並且在時間和空間複雜度上具有更小的常數。該算法由 Glenn K. Manacher 在 1975 年提出。

樸素算法

為了避免在之後的敍述中出現歧義，這裏我們指出什麼是「樸素算法」。

該算法通過下述方式工作：對每個中心位置 \(i\)，在比較一對對應字符後，只要可能，該算法便嘗試將答案加 \(1\)。

該算法是比較慢的：它只能在 \(O(n^2)\) 的時間內計算答案。

該樸素算法的實現如下：

實現

C++Python

vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {
  d1[i] = 1;
  while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
    d1[i]++;
  }

  d2[i] = 0;
  while (0 <= i - d2[i] - 1 && i + d2[i] < n &&
         s[i - d2[i] - 1] == s[i + d2[i]]) {
    d2[i]++;
  }
}

d1 = [0] * n
d2 = [0] * n
for i in range(0, n):
    d1[i] = 1
    while 0 <= i - d1[i] and i + d1[i] < n and s[i - d1[i]] == s[i + d1[i]]:
        d1[i] += 1

    d2[i] = 0
    while 0 <= i - d2[i] - 1 and i + d2[i] < n and s[i - d2[i] - 1] == s[i + d2[i]]:
        d2[i] += 1

Manacher 算法

這裏我們將只描述算法中尋找所有奇數長度子迴文串的情況，即只計算 \(d_1[]\)；尋找所有偶數長度子迴文串的算法（即計算數組 \(d_2[]\)）將只需對奇數情況下的算法進行一些小修改。

為了快速計算，我們維護已找到的最靠右的子迴文串的 邊界 \((l, r)\)（即具有最大 \(r\) 值的迴文串，其中 \(l\) 和 \(r\) 分別為該回文串左右邊界的位置）。初始時，我們置 \(l = 0\) 和 \(r = -1\)（-1需區別於倒序索引位置，這裏可為任意負數，僅為了循環初始時方便）。

過程

現在假設我們要對下一個 \(i\) 計算 \(d_1[i]\)，而之前所有 \(d_1[]\) 中的值已計算完畢。我們將通過下列方式計算：

如果 \(i\) 位於當前子迴文串之外，即 \(i > r\)，那麼我們調用樸素算法。

因此我們將連續地增加 \(d_1[i]\)，同時在每一步中檢查當前的子串 \([i - d_1[i] \dots i + d_1[i]]\)（\(d_1[i]\) 表示半徑長度，下同）是否為一個迴文串。如果我們找到了第一處對應字符不同，又或者碰到了 \(s\) 的邊界，則算法停止。在兩種情況下我們均已計算完 \(d_1[i]\)。此後，仍需記得更新 \((l, r)\)。
現在考慮 \(i \le r\) 的情況。我們將嘗試從已計算過的 \(d_1[]\) 的值中獲取一些信息。首先在子迴文串 \((l, r)\) 中反轉位置 \(i\)，即我們得到 \(j = l + (r - i)\)。現在來考察值 \(d_1[j]\)。因為位置 \(j\) 同位置 \(i\) 對稱，我們 幾乎總是 可以置 \(d_1[i] = d_1[j]\)。該想法的圖示如下（可認為以 \(j\) 為中心的迴文串被「拷貝」至以 \(i\) 為中心的位置上）：

\[ \ldots\ \overbrace{ s_l\ \ldots\ \underbrace{ s_{j-d_1[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_1[j]-1} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_1[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_1[j]-1} }_\text{palindrome}\ \ldots\ s_r }^\text{palindrome}\ \ldots \]

然而有一個 棘手的情況 需要被正確處理：當「內部」的迴文串到達「外部」迴文串的邊界時，即 \(j - d_1[j] + 1 \le l\)（或者等價的説，\(i + d_1[j] - 1 \ge r\)）。因為在「外部」迴文串範圍以外的對稱性沒有保證，因此直接置 \(d_1[i] = d_1[j]\) 將是不正確的：我們沒有足夠的信息來斷言在位置 \(i\) 的迴文串具有同樣的長度。

實際上，為了正確處理這種情況，我們應該「截斷」迴文串的長度，即置 \(d_1[i] = r - i\)。之後我們將運行樸素算法以嘗試儘可能增加 \(d_1[i]\) 的值。

該種情況的圖示如下（以 \(j\) 為中心的迴文串已經被截斷以落在「外部」迴文串內）：

\[ \ldots\ \overbrace{ \underbrace{ s_l\ \ldots\ s_j\ \ldots\ s_{j+(j-l)} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)}\ \ldots\ s_i\ \ldots\ s_r }_\text{palindrome} }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here} \]

該圖示顯示出，儘管以 \(j\) 為中心的迴文串可能更長，以致於超出「外部」迴文串，但在位置 \(i\)，我們只能利用其完全落在「外部」迴文串內的部分。然而位置 \(i\) 的答案可能比這個值更大，因此接下來我們將運行樸素算法來嘗試將其擴展至「外部」迴文串之外，也即標識為 "try moving here" 的區域。

最後，仍有必要提醒的是，我們應當記得在計算完每個 \(d_1[i]\) 後更新值 \((l, r)\)。

同時，再讓我們重複一遍：計算偶數長度迴文串數組 \(d_2[]\) 的算法同上述計算奇數長度迴文串數組 \(d_1[]\) 的算法十分類似。

Manacher 算法的複雜度

因為在計算一個特定位置的答案時我們總會運行樸素算法，所以一眼看去該算法的時間複雜度為線性的事實並不顯然。

然而更仔細的分析顯示出該算法具有線性複雜度。此處我們需要指出，計算 Z 函數的算法和該算法較為類似，並同樣具有線性時間複雜度。

實際上，注意到樸素算法的每次迭代均會使 \(r\) 增加 \(1\)，以及 \(r\) 在算法運行過程中從不減小。這兩個觀察告訴我們樸素算法總共會進行 \(O(n)\) 次迭代。

Manacher 算法的另一部分顯然也是線性的，因此總複雜度為 \(O(n)\)。

Manacher 算法的實現

分類討論

為了計算 \(d_1[]\)，我們有以下代碼：

C++Python

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
    k++;
  }
  d1[i] = k--;
  if (i + k > r) {
    l = i - k;
    r = i + k;
  }
}

d1 = [0] * n
l, r = 0, -1
for i in range(0, n):
    k = 1 if i > r else min(d1[l + r - i], r - i + 1)
    while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
        k += 1
    d1[i] = k
    k -= 1
    if i + k > r:
        l = i - k
        r = i + k

計算 \(d_2[]\) 的代碼十分類似，但是在算術表達式上有些許不同：

C++Python

vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
    k++;
  }
  d2[i] = k--;
  if (i + k > r) {
    l = i - k - 1;
    r = i + k;
  }
}

d2 = [0] * n
l, r = 0, -1
for i in range(0, n):
    k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
    while 0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]:
        k += 1
    d2[i] = k
    k -= 1
    if i + k > r:
        l = i - k - 1
        r = i + k

統一處理

雖然在講解過程及上述實現中我們將 \(d_1[]\) 和 \(d_2[]\) 的計算分開考慮，但實際上可以通過一個技巧將二者的計算統一為 \(d_1[]\) 的計算。

給定一個長度為 \(n\) 的字符串 \(s\)，我們在其 \(n + 1\) 個空中插入分隔符 \(\#\)，從而構造一個長度為 \(2n + 1\) 的字符串 \(s'\)。舉例來説，對於字符串 \(s = \mathtt{abababc}\)，其對應的 \(s' = \mathtt{\#a\#b\#a\#b\#a\#b\#c\#}\)。

對於字母間的 \(\#\)，其實際意義為 \(s\) 中對應的「空」。而兩端的 \(\#\) 則是為了實現的方便。

注意到，在對 \(s'\) 計算 \(d_1[]\) 後，對於一個位置 \(i\)，\(d_1[i]\) 所描述的最長的子迴文串必定以 \(\#\) 結尾（若以字母結尾，由於字母兩側必定各有一個 \(\#\)，因此可向外擴展一個得到一個更長的）。因此，對於 \(s\) 中一個以字母為中心的極大子迴文串，設其長度為 \(m + 1\)，則其在 \(s'\) 中對應一個以相應字母為中心，長度為 \(2m + 3\) 的極大子迴文串；而對於 \(s\) 中一個以空為中心的極大子迴文串，設其長度為 \(m\)，則其在 \(s'\) 中對應一個以相應表示空的 \(\#\) 為中心，長度為 \(2m + 1\) 的極大子迴文串（上述兩種情況下的 \(m\) 均為偶數，但該性質成立與否並不影響結論）。綜合以上觀察及少許計算後易得，在 \(s'\) 中，\(d_1[i]\) 表示在 \(s\) 中以對應位置為中心的極大子迴文串的 總長度加一。

上述結論建立了 \(s'\) 的 \(d_1[]\) 同 \(s\) 的 \(d_1[]\) 和 \(d_2[]\) 間的關係。

由於該統一處理本質上即求 \(s'\) 的 \(d_1[]\)，因此在得到 \(s'\) 後，代碼同上節計算 \(d_1[]\) 的一樣。

練習題目

本頁面主要譯自博文 Нахождение всех подпалиндромов 與其英文翻譯版 Finding all sub-palindromes in \(O(N)\)。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用