Manacher 算法学习笔记

马拉车算法是一个高效求解最长回文子串的算法。

这是模板题

传统的暴力方法是枚举回文子串中点，向两端扩展至无法继续扩展时更新答案，复杂度是 \(O(n^2)\) 的，效率并不算高。

我们注意到，回文串具有对称性，能不能利用这个性质减少运算量呢？

首先我们要对原来的字符串做点小小的处理。回文串的长度可能是偶数，这种情况下枚举回文串的中点非常难搞。

我们可以在原字符串的相邻两个字符之间，以及字符串最前面和最后面插入一些其他字符（比如说#号），这样所有回文串的长度就都是奇数啦！

QAQQwQ

->#Q#A#Q#Q#w#Q#

我们定义 \(f_i\) 表示以 \(i\) 为对称中心的回文串的最大半径（即从中心到最左/右端的长度），\(maxr\) 表示目前已经访问到的最右端的字符，\(mid\) 表示右端为 \(maxr\) 的最长回文子串的对称中心。

和传统算法一样，我们还是从左到右枚举对称中心 \(i\)。但是我们可以利用回文串的对称性减少一部分运算量。

当 \(i<maxr\) 时，我们可以利用之前已经算出来的信息来减少运算量。

设 \(i\) 关于 \(mid\) 的对称点为 \(j=2 \times mid-i\)。这时，根据 \(mid\) 的定义，我们可以直接将 \(f_i\) 的值设置成 \(f_j\)。当然，考虑到 \(i+f_i \leq maxf\) 的这一性质，实际上：

$$f_i=\min(f_j,f_{mid}+mid-i)$$

如果\(i>maxr\)，以前的信息就没有用了，\(f_i=1\)。

接下来，我们还是采用传统的暴力方法向两端扩展，同时更新\(f_i,mid,maxr\)。

马拉车的时间复杂度？乍一看并不显然。

因为 \(maxr\) 最多右移 \(n\)，复杂度是 \(O(n)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[11000005],s[25000005];
int f[25000005];
void init()
{
 s[0]=s[1]='#';//0位置防止越界
 int len=strlen(a);
 for(int i=0;i<len;i++)
 {
  s[2*i+2]=a[i];
  s[2*i+3]='#';
 }
 s[2*len+2]=0;
}
int main()
{
 int ans=0;
 scanf("%s",a);
 init();
 int len=strlen(s),maxr=0,mid=0;
 for(int i=1;i<len;i++)
 {
  if(i<maxr)
   f[i]=min(f[mid]+(mid-i),f[mid*2-i]);
  else f[i]=1;
  while(s[i+f[i]]==s[i-f[i]])
   f[i]++;
  if(f[i]+i>maxr)
  {
   maxr=f[i]+i;
   mid=i;
  }
  ans=max(ans,f[i]);
 }
 printf("%d\n",ans-1);
 return 0;
}