今天讲的字符串哈希题觉得都很水啊，咋一听到 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)\) 的。

1
2
3
4
5
6
7
8
9
10
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。