首页 > 代码库 > BZOJ2565 最长双回文串
BZOJ2565 最长双回文串
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
题目链接:BZOJ2565
正解:$manacher$
解题报告:
直接跑一遍$manacher$,然后我只需要找到一个分隔符的位置,考虑两边能拓展的最大值。
那么我预处理出$L[i]$和$R[i]$,分别表示能覆盖$i$的最左端点,能覆盖$i$的最右端点,对于每个分隔符所在的位置算一遍贡献就可以了。
//It is made by ljh2000 //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <ctime> #include <vector> #include <queue> #include <map> #include <set> #include <string> #include <complex> #include <bitset> using namespace std; typedef long long LL; typedef long double LB; typedef complex<double> C; const double pi = acos(-1); const int MAXN = 200011; int n,p[MAXN],tot,ans,L[MAXN],R[MAXN]; char ch[MAXN],s[MAXN]; inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline void manacher(){ tot=1; s[0]=‘%‘; s[1]=‘#‘; for(int i=1;i<=n;i++) { s[++tot]=ch[i]; s[++tot]=‘#‘; } int mx=0,id; for(int i=1;i<=tot;i++) { if(i<=mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1; for(;i+p[i]<=tot && s[i+p[i]]==s[i-p[i]];p[i]++) ; if(i+p[i]>mx) { mx=i+p[i]; id=i; } } for(int i=1;i<=tot;i++) p[i]--; } inline void work(){ scanf("%s",ch+1); n=strlen(ch+1); manacher(); ans=2; int mx=1; for(int i=1;i<=tot;i++) for(;mx<=i+p[i];mx++) L[mx]=i; int mn=tot; for(int i=tot;i>=1;i--) for(;mn>=i-p[i];mn--) R[mn]=i; for(int i=1;i<n;i++) ans=max(ans,R[2*i+1]-L[2*i+1]); cout<<ans; } int main() { work(); return 0; } //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
BZOJ2565 最长双回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。