题目

bzoj2565

输入长度为n(2<=n<=1e5)的串S，求S的最长双回文子串T，

即可将T分为两部分X，Y（|X|,|Y|≥1），且X和Y都是回文串。

思路来源

https://www.cnblogs.com/19992147orz/p/7553182.html 题解1

https://www.luogu.com.cn/blog/five20/solution-p4555 题解2

题解1

如果两个完整的回文串有交，显然把其中的一个降长度之后，能形成一个XY型双回文串

所以可以考虑枚举后面的最长单回文串，设其对应的开头的下标是i-p[i]，

则对于i-p[i]-1来说，需要找到以i-p[i]-1结尾的，最先出现的回文中心的位置，

这个可以考虑在扩展回文中心第一次扩展到i-p[i]-1的时候，记录一下

但是注意到，可能会有仅一个回文串的情形，

题解1代码需要特判，如aaaaa，abcba等等，前者答案仍为n，后者却为n-1

题解2

对于manacher算法来说，

p[i]-1是考虑#号时往一侧不考虑中心的半径长度，也是对应的原串的极长回文子串的长度

代码参考的题解2，考虑向左向右递推，只在每个极长回文子串的左端点、右端点处打标记

则两个标记点分别是i-p[i]+1和i+p[i]-1，极长回文串的长度为p[i]-1

而且标记点一定是#号，能将字母分隔开

对于左端点，就向右推-2标记；对于右端点，就向左推-2标记

则如果存在一个#号，既有左标记也有右标记，则构成合法答案

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N<<1;
int n,m,mx,pos,p[M],l[M],r[M],ans;
char s[M],t[N];
int main(){
    scanf("%s",t+1);
    n=strlen(t+1);
    s[0]='$';//串首串尾需不同 
    s[++m]='#';
    for(int i=1;i<=n;++i){
    	s[++m]=t[i];
		s[++m]='#';
    }
    for(int i=1;i<=m;++i){
        if(i<mx){
        	p[i]=min(p[2*pos-i],mx-i);
        }
        else{
        	p[i]=1;
        } 
        while(s[i-p[i]]==s[i+p[i]]){
            p[i]++;
        }   
        if(i+p[i]>mx){
            pos=i;
            mx=i+p[i];
        }
        //printf("i:%d l:%d r:%d\n",i,i-p[i]+1,i+p[i]-1);
        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);
    }
    for(int i=1;i<=m;i+=2){
    	l[i]=max(l[i],l[i-2]-2);
    }
	for(int i=m;i>=1;i-=2){
		r[i]=max(r[i],r[i+2]-2);
	}
	for(int i=1;i<=m;i+=2){//枚举#号 
		//printf("i:%d l:%d r:%d\n",i,l[i],r[i]);
		if(l[i] && r[i]){
			ans=max(ans,l[i]+r[i]); 
		}
	}
	printf("%d\n",ans);
    return 0;
}