首页 > 代码库 > BZOJ2565: 最长双回文串
BZOJ2565: 最长双回文串
2565: 最长双回文串
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 617 Solved: 330
[Submit][Status]
Description
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
Input
一行由小写英文字母组成的字符串S。
Output
一行一个整数，表示最长双回文子串的长度。
Sample Input
baacaabbacabb
Sample Output
12
HINT
样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
数据规模及限制
对于10%的数据，2≤|S|≤103。
对于30%的数据，2≤|S|≤104。
对于100%的数据，2≤|S|≤105。
Source
2012国家集训队Round 1 day2
题解：刚开始看见没什么思路。
后来想了想，定义f[i]表示以i结尾的最长回文字串求出f就可以了。
然后有发现 对于一个i，如果回文中心 j j+p[j]>i,那么j可以更新i，显然回文的中心j越小说明f[i]越大，那么我们就可以线段树来搞一个最小值的区间修改和查询了。
然后发现这题有点特殊，最优值是越来越差的，那么我们前面已经覆盖了的点就不用再覆盖了，所以可以直接暴力扫过去，用last表示更新到哪个节点。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,f[maxn],g[maxn],p[maxn],s[maxn]; 61 char st[maxn]; 62 63 int main() 64 65 { 66 67 freopen("input.txt","r",stdin); 68 69 freopen("output.txt","w",stdout); 70 71 scanf("%s",st+1);n=strlen(st+1); 72 for1(i,n)s[i<<1]=st[i];n<<=1;n++; 73 for(int i=1;i<=n;i+=2)s[i]=0; 74 int id=0,mx=0; 75 for(int i=1;i<=n;i++) 76 { 77 if(mx>i)p[i]=min(p[2*id-i],mx-i); 78 while(i-p[i]>0&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]])p[i]++; 79 if(i+p[i]>mx)mx=i+p[i],id=i; 80 } 81 int last=0; 82 for1(i,n) 83 if(i+p[i]>last) 84 { 85 for(int j=last+1;j<i+p[i];j++) 86 if(s[j])f[j]=j-i+1; 87 last=i+p[i]-1; 88 } 89 last=n+1; 90 for3(i,n,1) 91 if(i-p[i]<last) 92 { 93 for(int j=last-1;j>i-p[i];j--) 94 if(s[j])g[j]=i-j+1; 95 last=i-p[i]+1; 96 } 97 int ans=0; 98 for1(i,n-1)if(s[i]!=(int)‘#‘)ans=max(ans,f[i]+g[i+2]); 99 //for1(i,n)cout<<i<<‘ ‘<<s[i]<<‘ ‘<<p[i]<<‘ ‘<<f[i]<<‘ ‘<<g[i]<<endl;100 printf("%d\n",ans);101 102 return 0;103 104 }
BZOJ2565: 最长双回文串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。