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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注