Manacher笔记

11jiang08 / 2023-08-21 / 原文

Manacher 算法应用于一种特定的场景：查找一个长度为 \(n\) 的字符串 \(S\) 的最长回文子串，Manacher 的复杂度为 \(O(n)\)，是这种场景中效率最高的算法。

首先对字符串 \(S\) 做一个变换来化简问题，原字符串的 “中心字符” 可能有一个或者两个。在 \(S\) 的每个字符左右各插入一个不属于 \(S\) 的字符（例如 #），此外为了防止越界，在 \(S\) 的首尾各加入两个其它不属于 \(S\) 的字符，经过变换后的字符串，不影响对其回文串的判定。

我们设 \(P_i\) 代表以 \(i\) 为中心字符的最长回文串的半径，答案为 \(\displaystyle \max_{1\le i \le |S|}\{P_i-1\}\)，这个最长回文子串在原字符串的开头位置是 \((i-P_i)/2\)。

如何高效的计算 \(P_i\)？其核心思想是利用 “回文的镜像也是回文” 的特征减少重复。

设当前已经计算出 \(P_{0 \sim i-1}\) 的值，下一步继续计算 \(P_i\)，设 \(R\) 为 \(P_{0 \sim i-1}\) 中所有回文串的最大右端点，\(C\) 是 \(R\) 对应的回文串，也就是说，\(R=\displaystyle\max_{0 \le C \le i-1}\{C+P_C\}\)。

设 \(j\) 是 \(i\) 关于 \(C\) 的镜像点，显然 \(P_j\) 已经被计算。

\(i \ge R\)：此时只能设 \(P_i=1\)，然后暴力拓展 \(P_i\)。

\(i <R\)：细分两种情况讨论

\(j\) 的回文串被 \(C\) 的回文串包含：根据镜像原理，镜像 \(i\) 的回文不会越过 \(R\)，有 \(P_i=P_j=P_{2C-i}\)，然后继续用暴力拓展法。
\(j\) 的回文串不被 \(C\) 的回文串包含：有 \(P[i]=R-i=C+P_C-i\)，然后继续用暴力拓展法。

以上两种情况可以一起处理，\(P_i\) 取两者的最小值。

#include<bits/stdc++.h>
using namespace std;
const int N=3e7+7;
char s[N],str[N];
int n,p[N],ans;
void manacher(){
    int k=0;
    str[k++]='$';  str[k++]='#';
    for(int i=0;i<n;i++){
        str[k++]=s[i];
        str[k++]='#';
    }
    str[k++]='&';
    n=k;
    int R=0,C=0;
    for(int i=1;i<n;i++){
        if(i<R)  p[i]=min(p[2*C-i],C+p[C]-i);
        else  p[i]=1;
        while(str[i+p[i]]==str[i-p[i]])  p[i]++;
        if(p[i]+i>R){R=p[i]+i;C=i;}
        ans=max(ans,p[i]);
    }
}
int main(){
    scanf("%s",s);  n=strlen(s);
    manacher();
    cout<<ans-1;
    return 0;
}