manacher模板(manacher)

时间:2023-03-08 16:21:36
manacher模板(manacher)

洛谷题目传送门

写完有一段时间了,发现板子忘记存在了这里。。。。。。

算法简述

一种字符串算法,\(O(n)\)高效求出以每个字符为对称中心的最长回文串长度。

然后,就可以进一步求出全串中最长回文串的长度,以及全串回文子串总数。

这篇博客已经讲的很清楚了。

有一个小细节还需要提一下。为了方便判断下标是否越界问题,我们可以这样做——将字符串从一号下标开始存储,然后在零号下标放一个与串中所有字符都不同的字符(包括中间插入的字符)。这样在扫到边界的时候,一定会匹配失败。这样少写了好几个if,非常方便。

其它就没什么问题了。模板如下:

#include<cstdio>
char s[23333333];
int f[23333333];
inline int min(register int x,register int y){return x<y?x:y;}
int main()
{
register int len,i,l,r,mr=0,m=0,ans=0;
s[0]='~';s[1]='%';//上面提到的小细节
for(len=2;(s[len]=getchar())>='a';len+=2)
s[len|1]='%';
for(i=1;i<len;++i)
{
if(i<mr)f[i]=min(f[(m<<1)-i],mr-i);//最大化利用前面的信息
for(l=i-f[i]-1,r=i+f[i]+1;s[l]==s[r];--l,++r,++f[i]);//继续向两侧匹配
if(mr<r-1)mr=r-1,m=i;//更新最大可行右端点
if(ans<f[i])ans=f[i];//更新最大长度
}
printf("%d\n",ans);
return 0;
}

另外,向中间插入使得字符串长度增加了一倍。我在洛谷rank榜第一名的代码中看到,这位神犇居然没插字符!时间也基本比我少一半。

我还是懒得整理啦(其实是因为我太菜了)。可能会对奇数长度回文子串和偶数长度回文字串进行分别处理吧。有兴趣的博友们可以自己研究一下哦!