Manacher

引入

Manacher 算法可以在 $O(n)$ 的时间内求出一个字符串中的最长回文串

先需要改造原字符串，在字符之间和两端插入 #，改造后，都变成了奇回文串，并把 $s[0]$ 改成 $

那么，aba 就改造成 $#a#b#a# 了

我们定义回文半径 $d[i]$ 表示以 $i$ 为中心的最长回文串的长度的一半，叫回文半径

加速盒子 $[l,r]$，算法过程中我们维护右端点最靠右的最长回文串，利用盒子，借助之前的状态来加速计算的状态，具体的来说，盒内的 $d[i]$ 可以利用对称点的 $d$ 值来转移，盒外暴力

实现

计算前 $i-1$ 个 $d$ 函数，维护盒子 $[l,r]$

1. 如果 $i\le r$ ，则 $i$ 的对称点为 $r-i+l$
   • 若 $d[r-i+1]<r-i+1$ ，则 $d[i]=d[i-l+1]$
   • 若 $d[r-i+1]\le r-i+1$ ，则令 $d[i]=r-i+1$，从 $r+1$ 往后暴力枚举
2. 如果 $i>r$ ，则从 $i$ 开始暴力枚举
3. 求出 $d[i]$ 后，如果 $i+d[i]-1>r$ ，则更新盒子 $l=i-d[i]+1,r=i+d[i]-1$

auto manacher(string a) {
    string s = "$#";
    for (int i = 0; i < a.size(); i++) 
        s += a[i], s += '#';
    vector<int> d(s.size());
    d[1] = 1;
    for (int i = 2, l, r = 1; i < s.size(); i++) {
        if (i <= r) d[i] = min(r - i + 1, d[r - i + l]);
        while (s[i - d[i]] == s[i + d[i]]) d[i] ++;
        if (i + d[i] - 1 > r) 
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}