【模板】Manacher 回文串

【模板】Manacher 回文串

推荐两个讲得很好的博客:

  http://blog.sina.com.cn/s/blog_70811e1a01014esn.html

  https://segmentfault.com/a/1190000003914228

 #include<cstring>
#include<cstdio>
#include<algorithm>
#define N (22000010)
using namespace std;
int n, ans, mid, mx;
int p[N];
char tmp[N],s[N];
inline int max(int a, int b){return a>b?a:b;}
int main(){
scanf("%s", tmp+); n=strlen(tmp+);
for(int i=;i<=n;i++) s[i<<]=tmp[i], s[i<<|]='#';
n=(n<<)+;
s[]=s[n]='#';
ans=mid=mx=;
for(int i=;i<=n;i++){
if(mx>i) p[i]=min(p[(mid<<)-i],mx-i);
else p[i]=;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(p[i]+i>mx) mx=p[i]+i, mid=i;
ans=max(ans, p[i]);
}
return printf("%d\n", ans-),;
}

洛谷 3805

上一篇:Manacher回文串算法学习记录


下一篇:Effective C++ -----条款22:将成员变量声明为private