题目描述：
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
算法标签：manacher,线段树
思路：
用manacher求出以每个点为中心的最长回文串，对于区间[i-rad[i],i]里包含的点x,以x点为左端点的回文串长度为i-x+1，对于区间[i,i+rad[i]]同理处理以区间内的点为右端点的情况，两棵线段树维护。
以下代码：
#include<bits/stdc++.h> #define il inline using namespace std; const int N=2e5+5; char a[N],s[N];int mn[N<<1],mx[N<<1],ans,tot,n,rad[N]; il void manacher(){ for(int i=2,j=0,k;i<=tot;i+=k){ while(s[i-j-1]==s[i+j+1])j++;rad[i]=j; for(k=1;k<=rad[i]&&rad[i]-k!=rad[i-k];k++){ rad[i+k]=min(rad[i-k],rad[i]-k); } j=max(j-k,0); } } il void init(int x,int l,int r){ mn[x]=r<<1;mx[x]=l<<1;if(l==r)return; int mid=(l+r)>>1;init(x<<1,l,mid);init(x<<1|1,mid+1,r); } il void insmn(int x,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){mn[x]=min(mn[x],v);return;} int mid=(l+r)>>1; if(ql<=mid)insmn(x<<1,l,mid,ql,qr,v); if(mid<qr)insmn(x<<1|1,mid+1,r,ql,qr,v); } il void insmx(int x,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){mx[x]=max(mx[x],v);return;} int mid=(l+r)>>1; if(ql<=mid)insmx(x<<1,l,mid,ql,qr,v); if(mid<qr)insmx(x<<1|1,mid+1,r,ql,qr,v); } il int qmn(int x,int l,int r,int pos){ if(l==r)return mn[x];int mid=(l+r)>>1; if(pos<=mid)return min(qmn(x<<1,l,mid,pos),mn[x]); else return min(qmn(x<<1|1,mid+1,r,pos),mn[x]); } il int qmx(int x,int l,int r,int pos){ if(l==r)return mx[x];int mid=(l+r)>>1; if(pos<=mid)return max(qmx(x<<1,l,mid,pos),mx[x]); else return max(qmx(x<<1|1,mid+1,r,pos),mx[x]); } int main() { scanf(" %s",a+1);n=strlen(a+1);s[++tot]='#'; for(int i=1;i<=n;i++)s[++tot]=a[i],s[++tot]='#'; manacher();init(1,1,n); for(int i=2;i<=tot;i++){ if(!rad[i])continue; if(i&1){ insmx(1,1,n,(i-rad[i]+1)>>1,(i-1)>>1,i+1); insmn(1,1,n,(i+1)>>1,(i+rad[i]-1)>>1,i-1); } else{ insmx(1,1,n,(i-rad[i]+1)>>1,i>>1,1+i); insmn(1,1,n,i>>1,(i+rad[i]-1)>>1,i-1); } } for(int i=2;i<=n;i++){ ans=max(-qmn(1,1,n,i-1)-2+qmx(1,1,n,i),ans); }printf("%d ",ans); return 0; }