Manacher

今天讲的字符串哈希题觉得都很水啊，咋一听到 Manacher 题就懵逼了呢？重学一遍……

简介

给定一个长度为 $n$ 的字符串 $S$，找到所有回文子串。
最坏情况下有 $O(n^2)$ 个回文串，为了做到线性，我们使用回文半径来表示回文。这样，我们要求的就转化为：对于每个位置 $i$，求出最长回文半径。
使用字符串哈希可以容易地在 $O(n\log n)$ 时间内解决，但 Manacher 更为简洁和高效。

实现过程

约定：$[l,r]$ 表示下标在 $l,r$ 之间的子串。
我们只考虑长度为奇数的回文串，可以通过在字符串每个字符间加入无关字符如 # 等来把长度为偶数的串转化为长度为奇数的串。接下来，我们维护 $p_i$ 表示以 $i$ 为重心的回文半径，$r$ 为当前找到的覆盖位置最靠右的回文串能覆盖到的最大下标，$mid$ 表示它的回文中心的下标。
计算过程考虑分类讨论：

• $i>r$ 时，直接暴力一步步向后跳。
• $i\le r$ 时，设 $j$ 为 $i$ 关于 $mid$ 的对称点，即 $mid\times 2-i$。
  由于 $[j-p_j,j+p_j]$ 与 $[i-p_i,i+p_i]$ 相等且都是回文串，所以 $p_i$ 可以直接取 $p_j$ 的值。但这个推论成立当且仅当 $i+p_j\le r$，否则 $p_i$ 只能取到 $r-i+1$，然后再暴力扩展。
  综上，$p_i=\min(p_j,r-i+1)$。

$r$ 只能向右移动，故最多移动 $O(n)$ 次。其余情况的计算显然是 $O(1)$ 的。

for(int i=1,r=0,mid=0;i<=n;i++){
    int j=2*mid-i;
    if(i<=r) p[i]=min(r-i+1,p[j]);
    else p[i]=1;
    while(s[i-p[i]]==s[i+p[i]]) ++p[i];
    if(i+p[i]-1>r){
        r=i+p[i]-1;
        mid=i;
    }
}

部分引自 https://oi-wiki.org/string/manacher/

非常感谢这篇博客，讲的很透彻，帮我彻底弄懂了 Manacher。
https://www.luogu.com.cn/article/2fmdma9m