广州网站设计教程,学编程好找工作吗?,手机网站可以做动态吗,景翔物流网站建设公司题目描述 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串#xff0c;而abc不是#xff08;abc的顺序为abc#xff0c;逆序为cba#xff0c;不相同#xff09;。 输入长度为 n的串 S #xff0c;求 S的最长双回文子串 T ,即可将 T 分为两部分 X#xff0c; … 题目描述 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串而abc不是abc的顺序为abc逆序为cba不相同。 输入长度为 n的串 S 求 S的最长双回文子串 T ,即可将 T 分为两部分 X Y ∣X∣,∣Y∣≥1|X|,|Y|≥1∣X∣,∣Y∣≥1 且 X 和 Y 都是回文串。 输入输出格式 输入格式一行由小写英文字母组成的字符串 S 。 输出格式一行一个整数表示最长双回文子串的长度。 输入输出样例 输入样例#1 baacaabbacabb 输出样例#1 12 说明 【样例说明】 从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分且两者都是回文串。 对于100%的数据 2≤∣S∣≤105 Solution 本题$zyys$啊 很容易想到$manacher$于是先打个板子看看处理出以$i$为中心的最长回文半径$p[i]$后就断思路了。 我首先想到的是在每次更新$p[i]$后分别处理出以$i$为中心的半径$p[i]$内每个位置为开头和结尾的最长回文子串长度($manacher$结束后直接枚举断点就可以得到答案)但是这样强行又将复杂度拉到了$O(n^2)$。于是开始断线 后面看看巨佬们的思路豁然**我是真的蠢啊 其实将我开始的思路修改一下即可 我们维护最长回文半径$p[i]$的同时再分别维护两个东西以$i$为结尾的最长回文子串的长度$ll[i]$和以$i$为开头的最长回文子串的长度$rr[i]$。 那么很显然因为以$i$为中心的最长回文子串长度为$p[i]-1$所以每次更新$p[i]$后我们只需处理出当前这个回文子串的左右边界(中间的每个点的$ll[i],rr[i]$可以在$manacher$结束后$O(n)$处理出)则$ll[ip[i]-1]max(ll[ip[i]-1],p[i]-1)$(更新以$ip[i]-1$为结尾的最长回文长度)同理$rr[i-p[i]1]max(rr[i-p[i]1],p[i]-1)$。 跑完$manacher$后我们$O(n)$递推出每个$#$为断点的$ll[i]$和$rr[i]$其中$rr[i]$因为是$i$结尾的回文长度所以直接顺推每往后移一位最长回文子串长度$-2$于是$rr[i]max(rr[i],rr[i-2]-2)$($i-2$是上一个$#$位置)同理$ll[i]$直接逆推类似地$ll[i]max(ll[i],ll[i2]-2)$。 最后枚举每个$#$为断点更新$ans$就$OK$了。 代码 #includebits/stdc.h
#define For(i,a,b,c) for(int (i)(a);(i)(b);(i)(c))
#define Bor(i,a,b,c) for(int (i)(b);(i)(a);(i)-(c))
#define Min(a,b) ((a)(b)?(b):(a))
#define Max(a,b) ((a)(b)?(a):(b))
using namespace std;
const int N200050;
int p[N],ll[N],ans,rr[N],mx,id,cnt;
char s[N],t[N];
int main(){scanf(%s,t);int lenstrlen(t);s[cnt]$,s[cnt]#;For(i,0,len-1,1)s[cnt]t[i],s[cnt]#;s[cnt]\0;For(i,1,cnt,1){if(imx)p[i]Min(p[id*2-i],mx-i);else p[i]1;while(s[i-p[i]]s[ip[i]])p[i];if(mxip[i])idi,mxip[i];ll[ip[i]-1]Max(ll[ip[i]-1],p[i]-1);rr[i-p[i]1]Max(rr[i-p[i]1],p[i]-1);}For(i,2,cnt,2)rr[i]Max(rr[i],rr[i-2]-2);Bor(i,2,cnt,2)ll[i]Max(ll[i],ll[i2]-2);For(i,2,cnt,2)if(rr[i]ll[i])ansMax(ans,ll[i]rr[i]);coutans;return 0;
} 转载于:https://www.cnblogs.com/five20/p/9090876.html
