Manacher 算法

例题：P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。

Manacher 算法是一种快速找到字符串中所有回文串长度的线性算法。

奇偶回文长度统一处理

回文串存在两种形式：形如 $\texttt {abba}$ 的偶数回文串以及形如 $\texttt {abbcbba}$ 的奇数回文串。

我们令 $f_i (1 \le i \le |S|)$ 表示以第 $i$ 个字符串为中心形成的最长回文串，显然偶数回文串就不好处理了。

我们将每个字符之间用一个无关字符代替，例如 $\texttt{abba} \leftarrow \texttt{!a!b!b!a!}$。这样处理之后，每个偶回文串的中心就是无关字符了，可用来记录。与此同时，不难发现每个回文串的长度都增加了，设当前为 $f'_i$，原来为 $f_i$，不难发现：

$$\left \lfloor \frac{f'_i}{2} \right \rfloor = f_i$$

我们只需要记录当前点 $i$ 到达其中一端的距离便是原来的回文串长度 $f_i$，而这在 Manacher 算法里更加方便。

实现过程

对于一个穿 $S$，假设我们应处理完了前 $i - 1$ 个，并且第 $i - 1$ 个回文串的左右边界为 $l, r$。

对于当前的新下标 i，有如下几种情况：

• $i \gt r$，很显然，前面处理的都没有用，暴力循环记录即可。
• $i \lt r$，这说明 $f_i$ 有一部分是已经处理过的，而由于回文的对称性质，子串 $S[i, r]$ 和子串 $S[l, l + r - i]$ 互为逆字符串（当然前提是 $f_{l + r - i} \le i - l + 1$）。这又可以分为两种情况讨论：
  1. $f_{l + r - i} \le i - l + 1$：此时说明 $S[l, l + r - i]$ 与 $S[i, r]$ 可以匹配，但是 $r$ 右侧无法得知，暴力循环从 $r$​ 继续遍历即可。
  2. $f_{l + r - i} \gt l - i + 1$：此时说明 $S[l, r]$ 是回文串，$S[l + r - i - f_{l + r - i}, l + r - i + f_{l + r - i}]$ 也属于回文串，f_i 此时不能再向右侧扩展，故 $f_i \leftarrow f_{l + r - 1}$。

时间复杂度分析

由上述过程可知，每一次循环都要判断右边界 $r$，并且每一次循环都会使得 $r \leftarrow r + 1$，由于 $r$ 只会增加到 $|S|$，因此时间复杂度为 $O(|S|)$，即线性复杂度。

代码实现

预处理：

1
2
3
4

s[0] = '#';
    for (int i = 0; i < str.size(); i ++)
        s[++ idx] = str[i], s[++ idx] = '#';
s[len = idx] = '#';

核心代码：

1
2
3
4
5
6
7

for (int i = 0, l = 0, r = -1; i <= len; i ++)
    {
        int k = (i > r) ? 1 : min(r - i + 1, ans[l + r - i]);
        while (i - k >= 0 && i + k <= len && s[i - k] == s[i + k]) k ++;
        ans[i] = k --;    // k - 1 的原因是此时中心由 i - 1 变成了 i
        if (i + k > r) r = i + k, l = i - k;    // 更新相对于 i 的 l 和 r
    }

Reference

Manacher - OI Wiki (oi-wiki.org)

P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)