首页 > 代码库 > BZOJ 2565: 最长双回文串
BZOJ 2565: 最长双回文串
2565: 最长双回文串
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1769 Solved: 895
[Submit][Status][Discuss]
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两部分,且两者都是回文串。
对于100%的数据,2≤|S|≤10^5
2015.4.25新加数据一组
Source
2012国家集训队Round 1 day2
分析:
首先用manacher求出每个点所能扩展的最长回文串,然后对于每个点记录l[i]r[i]代表以当前点结尾或者开头的最长回文串长度...
对于lr的求法有两种...一种是我这种比较low的求法...一种是LTY大佬边做manacher边求lr的%%%做法...
我的就不说了,看代码吧...表达能力2333...
LTY大佬说可以在manacher暴力匹配的时候(就是下面这句话...)
while(str[i-p[i]]==str[i+p[i]]) p[i]++;
这个时候可以更新暴力扩展的点的lr数组...%%%
代码:
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 //by NeighThorn 6 using namespace std; 7 //眉眼如初,岁月如故 8 9 const int maxn=200000+5; 10 11 int ans,len,p[maxn],l[maxn],r[maxn]; 12 13 char s[maxn],str[maxn]; 14 15 inline void prework(void){ 16 int i; 17 for(i=0;s[i];i++) 18 str[2*i+1]=‘#‘,str[(i+1)*2]=s[i]; 19 len=2*i+1;str[0]=‘$‘;str[len]=str[len+1]=‘#‘; 20 } 21 22 inline void manacher(void){ 23 int id,mx=0; 24 for(int i=1;i<len;i++){ 25 p[i]=i<mx?min(p[id*2-i],mx-i):1; 26 while(str[i-p[i]]==str[i+p[i]]) 27 p[i]++; 28 if(p[i]+i>mx) 29 mx=p[i]+i,id=i; 30 } 31 } 32 33 signed main(void){ 34 scanf("%s",s);ans=0; 35 prework();manacher(); 36 for(int i=1;i<=len;i++) 37 l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1),r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1); 38 for(int i=1;i<=len;i++){ 39 if(i&1) 40 l[i]=max(l[i],l[i-1]-2); 41 else 42 l[i]=max(l[i],l[i-1]); 43 } 44 for(int i=1;i<len;i++) 45 if(l[i]&&r[i]) 46 ans=max(ans,l[i]+r[i]); 47 printf("%d\n",ans); 48 return 0; 49 }//Cap ou pas cap. Pas cap.
By NeighThorn
BZOJ 2565: 最长双回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。