Created at 2021-04-13 18:24:39
Updated at 2023-10-18 10:41

Manacher Algorithm

“A new linear-time ‘on-line’ algorithm for finding the smallest initial palindrome of a string”
----Gleen K. Manacher (1975)

一种关于一个字符串 $S$ 的回文子串的算法, 可以线性求两个数组 $f_1$ 和 $f_2$, 分别表示以第 $i$ 位为中心的最长奇回文子串和最长偶回文子串的半径 (长度除以 $2$, 向上取整). 对于以 $i$ 为中心的回文子串 $[l, r]$, 规定 $i = \lceil \frac{l + r}2 \rceil$.

根据回文串的性质可以知道 ${f_1}_i$ 和 ${f_2}_i$ 也恰好是以 $i$ 为中心的回文子串的个数. 这条性质非常重要.

朴素

枚举每个回文中心 $i$ 每次从半径为 $1$ 开始, 每次验证是否可以增加半径.

容易看出, 这样最坏的复杂度可达 $O(n^2)$, 在 $s$ 形如 aaaa...aaaa 时可以出现.

不妨只考虑 $f_1$. 对于 $f_2$ ,除了有细节上的差别, 算法思想相同, 不再赘述.

优化

仍然是从小到大枚举回文中心 $i$, 可以认为求 ${f_1}_i$ 时, ${f_1}_j~(j \in [1, i))$ 已知.

设 $fr$ (fr) 为 $[1, i)$ 中, 令 $j + {f_1}_j - 1$ 最大的整数. 即 $[1, i)$ 中所有回文中心的最长的奇数长度回文子串中, $fr$ 的最长奇数长度回文子串右边界最靠右.

则对 $i$ 有两种情况:

• $i > fr + {f_1}_{fr} - 1$

这时的 $i$ 不在任何已知的回文子串中, 则直接朴素求 ${f_1}_i$.

• $i \leq fr + {f_1}_{fr} - 1$

这时的 $i$ 在以 $fr$ 为中心的回文串内, 记 $i$ 关于对称轴 $fr$ 的对称点为 $re$ (re). 易知 $re + i = 2fr$, 因此 $re = 2fr - i$.

因为 $re$ 在 $fr$ 左边, 所以 ${f_1}_{re}$ 已知, 所以可以求出 $re$ 为中心的奇数长度回文子串中, 完全被 $fr$ 的最长的奇数长度回文子串包含的最长回文子串半径为 $r$, 则这个子串关于 $fr$ 对称的子串也是回文串, 这个子串的中心恰为 $re$ 关于 $fr$ 的对称点 $i$.

我们已经得到了 $i$ 为中心的半径为 $r$ 的奇数长度回文子串, 因此 ${f_1}_i \geq r$.

我们接下来讨论被 $fr$ 为中心的奇数长度包含的最长的以 $re$ 为中心的奇数长度回文子串是否触及了边界:

• $i + r - 1 < fr + {f_1}_{fr} - 1$

以 $re$ 为中心的最长奇数长度回文子串和它外围的字符都被 $fr$ 的回文子串包含, 所以 $re$ 为中心的子串不再是回文的失配位置的对称点也应当是 $i$ 为中心的子串不再是回文的失配位置, 因此可以确定 ${f_1}_i = r$.

• $i + r - 1 = fr + {f_1}_{fr} - 1$

因为前面任何 $f1$ 值都没有描述 $i + r - 1$ 右边的情况, 因此在 ${f_1}_i \geq r$ 的基础上继续朴素即可, 无需从 $1$ 开始.

时间复杂度

求 Manacher 复杂度的核心在于求每次朴素的长度之和, 我们发现每次朴素地使某个核心的半径增加 $1$, $fr + {f_1}_{fr} - 1$ 就会向右移动一个字符, 而根据定义这个边界永远不会往回移动. 因此朴素的次数之和的复杂度为 $O(n)$, 其余部分对于每个 $i$ 都是 $O(1)$ 的, 因此总复杂度为 $O(n)$.

模板

一个长度为 $n$ 的字符串, 求最长回文子串长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

unsigned n, fr(0), Ans(0), Tmp(0), f1[11000005], f2[11000005];
char a[11000005];
int main() {
	fread(a+1,1,11000000,stdin);        // fread 优化 
  n = strlen(a + 1);                  // 字符串长度 
  a[0] = 'A';
  a[n + 1] = 'B';                     // 哨兵 
  for (register unsigned i(1); i <= n; ++i) {   // 先求 f1 
    if(i + 1 > fr + f1[fr]) {       // 朴素 
      while (!(a[i - f1[i]] ^ a[i + f1[i]])) {
        ++f1[i];
      }
      fr = i;                             // 更新 fr 
    }
    else {
      register unsigned re((fr << 1) - i), A(re - f1[re]), B(fr - f1[fr]);
      f1[i] = re - ((A < B) ? B : A);                      // 确定 f1[i] 下界 
      if (!(re - f1[re] ^ fr - f1[fr])) { // 特殊情况 
        while (!(a[i - f1[i]] ^ a[i + f1[i]])) {
          ++f1[i];
        }
        fr = i;                                           // 更新 fr 
      }
    }
    Ans = ((Ans < f1[i]) ? f1[i] : Ans);
  }
  Ans = (Ans << 1) - 1;                             // 根据 max(f1) 求长度 
  fr = 0;
  for (register unsigned i(1); i <= n; ++i) {
    if(i + 1 > fr + f2[fr]) {           // 朴素 
      while (!(a[i - f2[i] - 1] ^ a[i + f2[i]])) {
        ++f2[i];
      }
      fr = i;                                 // 更新 fr 
    }
    else {
      register unsigned re ((fr << 1) - i - 1), A(re - f2[re]), B(fr - f2[fr]);
        f2[i] = re - ((A < B) ? B : A);        // 确定 f2[i] 下界 
      if (A == B) { // 特殊情况, 朴素 
        while (a[i - f2[i] - 1] == a[i + f2[i]]) {
          ++f2[i];
        }
        fr = i;                               // 更新 fr 
      }
    }
    Tmp = ((Tmp < f2[i]) ? f2[i] : Tmp);
  }
  Tmp <<= 1;                                        // 根据 max(f2) 求长度 
  printf("%u\n", (Ans < Tmp) ? Tmp : Ans);          // 奇偶取其大 
  return Wild_Donkey;
}