Manacher

马拉车，主要用于解决回文子串的问题，其核心的思想就是“Mirrors”！

假设我们要确定一个回文串的中心和拓展长度，要如何实现？

先暴力

暴力想到的是对于每一个位置，我们都向左和向右进行拓展判断字符是否相等，如果相等则继续拓展 ——

int expand(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }

    return right - left - 1;
}

先有一个问题，对于一个位置来说，它可以作为中心点（奇数开始拓展），也可以和把中心点放在自己和隔壁字符的中间（偶数位置），这样的话就需要每次拓展两边

for (int i = 0; i < n; ++i) {
    int odd = expand(s, i, i);       // 奇数回文
    int even = expand(s, i, i + 1);  // 偶数回文
}

同时最坏的时间复杂度是 $O(N^2)$ —— 即每次左右拓展的时候都会扩很远，导致大量重复字符被匹配

马拉车

奇偶问题

由于著名的

$$\mathrm{奇}\mathrm{数}+\mathrm{偶}\mathrm{数}=\mathrm{奇}\mathrm{数}；\mathrm{偶}\mathrm{数}+\mathrm{奇}\mathrm{数}=\mathrm{奇}\mathrm{数}$$

所以当我把所有字符左右两边都插入一个特殊字符的话（并且把特殊字符也视作字符串中正普通的一个位置），就可以把奇偶问题化归成统一的奇数中心的回文串问题

例子

aba   -> #a#b#a#
abba  -> #a#b#b#a#

这样的话，所有的回文都会变成奇数长度的回文，有一个明确的字符作为中心

算法核心

也是复用已经匹配过的信息。

假设我们已有一个大的回文串，那么在其之中，i位置如果有回文半径，那么i的关于回文串中点的对称位置的回文半径也至少是i的大小（假设i的回文串也在大的回文串内）

好的，那么我们便不妨开一个数组存储当前位置的最长回文半径，同时维护一下在匹配过程中遇到的最靠右侧的回文串边界（因为从左往右进行扫描，所以最右侧的信息才更有可能被复用）

细节的，一般会把字符串左右分别加上“哨兵”以规避比较复杂的边界条件判断

具体流程

字符串预处理

首尾加“哨兵”，同时统一奇偶回文，比如对于s = "aba"

便拓展成t = "^#a#b#a#$"

扫描字符串

对于每一个中心i

• 如果i在当前右边界最远的回文区间（小于最右侧），则找到i的镜像位置，同时令p[i] = min(p[mirror], right - i)
  • 解释为什么是min(p[mirror], right - i)
  • 如果p[mirror]比较大，超出了当前最大回文区内部，那么不好意思，i位置超过最大回文区的信息我们无法确定，所以只能去二者的最小值
• 接着从当前p[i]开始，继续朝外扩展回文串长度
• 更新左右边界，在i + p[i]超过最右侧边界的时候

常见使用

可以做个预处理嘛，比如作为dp等其他算法的预处理步骤 —— 扫一遍就可以获得所有中心的最大回文半径