Manacher 总结

Mindeveloped's Factory / 2023-05-20 / 原文

1. 算法介绍

问题：有一个字符串 \(\texttt{str}\)，求解其中以每个字符为中心的最长奇回文子串以及以每两个字符为中心的最长偶回文子串。
目标复杂度：\(\Omicron(n)\)

首先是预处理，将原字符串中每两个字符之间加一个间隔符，即 \(S \gets *S_0*S_1*\cdots*S_n*\) 这样将偶回文串全部转换为奇回文串。
然后每个回文串的回文中心必为一个字符。定义这个字符到回文边界的距离叫做这个回文串的回文半径。
暴力做法：使用双指针算法，枚举每个点最大的回文半径。
复杂度：\(\Omicron(n^2)\)
这样的做法该如何优化呢？

考虑回文串的性质：回文串关于回文中心对称。
也就是说，若以 \(S_i\) 为中心的回文串 \(s\) 回文半径是 \(r\) ，则 \([i, i - r] = [i, i + r]\) 。
所以若 \(s\) 左半部分有一个子回文串，\(s\) 的右半部分必定会出现相同的子回文串。
对于回文中心右边的每个字符 \(S_x\)，考虑在回文串 \(s\) 中与其对称的字符 \(S_{2i - x}\)（记作 \(S_y\)）。
考虑以下几种情况：

\(y - r_y > i - r\) 这样的话由回文串的对称性，一定有 \([y - r_y, y + r_y] = [x - r_y, x + r_y]\) 是回文串，并且由于 \(r\) 是最大回文半径，所以一定有 \(S_{y - r_y - 1} = S_{x + r_y + 1} \neq S_{y + r_y + 1} = S_{x - r_y - 1}\)，所以 \(r_x = r_y\) 。
\(y - r_y = i - r\) 这种情况照样有上面的 \([y - r_y, y + r_y] = [x - r_y, x + r_y]\) 是回文串，但是由于 \(S_{y - r_y - 1}\) 会超出大回文串 \([i - r, i + r]\) 的边界，我们并不能保证 \(S_{y - r_y - 1} = S_{x + r_y + 1}\)，即可能会出现 \(S_{x - r_y - 1} = S_{x + r_y + 1}\)，所以 \(r_x \ge r_y\)。
\(y - r_y < i - r\) 由于 \([y - r_y, y + r_y]\) 已经超出了 \([i - r, i + r]\)，我们不能保证超出去的地方 \([y - r_y, i - r) = (i + r + 1, x + r_y + 1]\)，我们只能保证区间内的相等，此时 \(r_x \ge r\)。
由上面的情况得到，\(r_x \ge \min(r_y, r)\) 。
得到一个想法：如果选择了合适的 \(i\) 使当前的 \(x \in [i - r_i, i + r_i]\)，那么可以求得 \(r_x\) 的下限 \(\min(r_{2i - x}, i+r_i-x)\)，节约枚举的时间，且这个下限越大枚举花的时间越少。
然后就根据人类智慧（后面有证明）得出一个较为优秀的方法：选择右边界（即 \(i + r_i\)）最大的回文串作为 \(i\)。