Manacher笔记

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\) 已经被计算。

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

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

   1. \(j\) 的回文串被 \(C\) 的回文串包含：根据镜像原理，镜像 \(i\) 的回文不会越过 \(R\)，有 \(P_i=P_j=P_{2C-i}\)，然后继续用暴力拓展法。
   2. \(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;
   }