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$ $i < r$ ，这说明 $f_i$ $f_{i}$ 有一部分是已经处理过的，而由于回文的对称性质，子串 $S[i, r]$ $S [i, r]$ 和子串 $S[l, l + r - i]$ $S [l, l + r - i]$ 互为逆字符串（当然前提是 $f_{l + r - i} \le i - l + 1$ $f_{l + r - i} \leq 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|)$ ，即线性复杂度。

代码实现

预处理：

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

核心代码：

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
    }