首页 > 代码库 > bzoj 2565 manacher
bzoj 2565 manacher
2682. 【WC2012选拔12.17】最长双回文串 (Standard IO)
Time Limits: 2000 ms Memory Limits: 524288 KB
思路:
先做一遍MANACHER,然后枚举分界点(为#)
那么以这个点为分界的最长双回文串会由最左边的能覆盖到这个点的串和最右边的能覆盖到这个点的串组成
那么扫两遍求出每个点最左和最右能覆盖到它的回文串中心。(就是反过来求以每个点为中心的回文串能覆盖哪些点
然后枚举即可
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cstring>using namespace std;char s[200011];int r[200011],lm[200011],rm[200011];int i,n,x,z,q,len,j;char c;void Read(){ while(c=getchar(),c<‘a‘||c>‘z‘); s[++n]=‘#‘; s[++n]=c; while(c=getchar(),c>=‘a‘&&c<=‘z‘){ s[++n]=‘#‘; s[++n]=c; } s[++n]=‘#‘;}void Manacher(){ int i,len,l,k; len=0; for(i=1;i<=n;i++){ if(len<i){ l=0; while(s[i-l]==s[i+l]&&i-l>=1&&i+l<=n)l++; r[i]=l; } else{ l=min(len-i+1,r[k+k-i]); while(s[i+l]==s[i-l]&&i-l>=1&&i+l<=n)l++; r[i]=l; } if(i+r[i]-1>len){ len=i+r[i]-1; k=i; } }}int main(){ Read(); Manacher(); r[0]=0; len=0; for(i=1;i<=n;i++){ if(i+r[i]-1>len){ for(j=len+1;j<=i+r[i]-1;j++)lm[j]=i; len=i+r[i]-1; } if(len==n)break; } len=n+1; for(i=n;i>=1;i--){ if(i-r[i]+1<len){ for(j=i-r[i]+1;j<=len-1;j++)rm[j]=i; len=i-r[i]+1; } if(len==1)break; } for(i=1;i<=n;i++)if(s[i]==‘#‘){ z=(rm[i]-i+1)*2-1+(i-lm[i]+1)*2-1-1; if(z/2>q)q=z/2; } printf("%d\n",q);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。