BZOJ 2565: 最长双回文串

2565: 最长双回文串

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1769 Solved: 895
[Submit][Status][Discuss]

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

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

秒客网