2565: 最长双回文串
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2313 Solved: 1166
[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
12
HINT
样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5
2015.4.25新加数据一组
题解：
不难想到，对于每一个位置i，我们如果找到以它为右端点最多能往左延伸到多远，以及以它为左端点往右能延伸到多远，那么我们就可以得到这个点的答案，再枚举所有的i，假设i为两个回文子串的断点，就可以得到答案呢。
如何找到以i为右端点的答案呢？右端点固定以后，要让左边的回文串尽可能大，那么左边的中心位置就应该尽可能地偏左。我们从左往右枚举中心位置的时候，正好就满足了单调性，所以对一个子串，如果之前没有串能到达这个位置，那么就把这个位置标记给这个串。如果之前这个位置已经被标记过了，就不管了。左端点同理。
如何得到答案？这样得到的两个端点显然是可能有重复的地方。
考虑两个串a，b，假设两个串重复覆盖的长度为d，那么两个串实际覆盖的长度为a+b-d。问题就转化为了如何继续两个串的重复覆盖长度。找到i以右的端点br[i]，再找到以br[i]为中心位置的左端点l，同理找到以bl[i]为中心的右端点r，重复覆盖的长度就是r-l+1。然后最后肯定要计算i位置，所以长度+1。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100100;
char s[N<<1];
int l[N],bl[N<<1],val[N<<1],br[N<<1];
int m;
inline int Min(int a,int b){
return a<b?a:b;
}
inline int Max(int a,int b){
return a>b?a:b;
}
void manacher(int len){
m=len<<1;
for(register int i=len;i>=0;i--){
s[(i+1<<1)]=s[i];
s[(i<<1)+1]='#';
}
s[0]='+';
int mx=0,id;
for(register int i=1;i<=m;i++){
if(mx>=i) val[i]=Min(mx-i+1,val[2*id-i]);
else val[i]=1;
while(s[i-val[i]]==s[i+val[i]]) val[i]++;
if(i+val[i]-1>mx) mx=i+val[i]-1,id=i;
}
}
#define ms(x,y) memset(x,y,sizeof(x))
int main(){
ms(bl,-1);ms(br,-1);
scanf("%s",s);
int len=strlen(s);
manacher(len);
for(register int i=1;i<=m;i++){
if(val[i]>1){
for(register int j=i+val[i]-1;j>=i-val[i]+1;j--)
if(bl[j]==-1) bl[j]=i;
else break;
}
}
for(register int i=m;i>=1;i--){
if(val[i]>1){
for(register int j=i-val[i]+1;j<=i+val[i]-1;j++)
if(br[j]==-1) br[j]=i;
else break;
}
}
int mmax=0;
for(register int i=1;i<m;i++){
int l=br[i]-val[br[i]]+1;
int r=bl[i]+val[bl[i]]-1;
int ans=r-l+1;
/*printf("%d :",i);
printf("%d %d ",bl[i],val[bl[i]]);
printf("%d %d ",br[i],val[br[i]]);
printf("%d\n",ans); */
//val[bl[i]]-1 实际的字符串的长度
mmax=Max(mmax,(val[bl[i]]-1+val[br[i]]-1)-(ans-1));
//-1 i位置
}
printf("%d\n",mmax);
return 0;
}