题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
输入
一行由小写英文字母组成的字符串S。
输出
一行一个整数,表示最长双回文子串的长度。样例输入
baacaabbacabb样例输出
12提示
样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。
对于100%的数据,2≤|S|≤10^5
我们假设中间添加的间隔字符是'&',那么只要知道以每个'&'结尾和开头的最长回文串长度之和然后取最大值即可得到答案。因为求以每个'&'结尾和开头的最长回文串的方法一样,所以我们以求结尾的为例(变量名为$lmx$)。对于第$i$个字符,它的回文半径为$l_{i}$,那么$[i,i+l_{i}-1]$的$lmx$都会更新,但显然不能一个一个更新。我们发现对于$lmx[i+l_{i}-1]$会被$l_{i}-1$更新(去掉回文串中的'&'),而$lmx[i+l_{i}-3]$会被$l_{i}-3$更新,所以只要$lmx[i]=max(lmx[i],lmx[i+2]-2)$这样从右往左更新一遍即可,求开头的同理。注意要保证双回文串的两个回文串都非空。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; char s[200010]; int n; int len[200010]; int l[200010]; int r[200010]; int ans; int mx,num; int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=n;i>=1;i--) { s[i<<1]=s[i]; s[i<<1|1]='&'; } n=n<<1|1; s[0]='%'; s[1]='&'; s[n+1]='^'; for(int i=1;i<=n;i++) { len[i]=mx>=i?min(len[2*num-i],mx-i+1):1; while(s[i+len[i]]==s[i-len[i]]) { len[i]++; } if(mx<i+len[i]-1) { mx=i+len[i]-1; num=i; } r[i-len[i]+1]=max(r[i-len[i]+1],len[i]-1); l[i+len[i]-1]=max(l[i+len[i]-1],len[i]-1); } for(int i=1;i<=n;i+=2) { r[i]=max(r[i],r[i-2]-2); } for(int i=n;i>=1;i-=2) { l[i]=max(l[i],l[i+2]-2); } for(int i=1;i<=n;i+=2) { if(l[i]&&r[i]) { ans=max(ans,l[i]+r[i]); } } printf("%d",ans); }