Description
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
Solution
这题就是求对于每个前缀 S[1..i] ，求它的最长回文后缀，然后正反做一次，枚举分界点对答案取最大值即可。
那么有经典回文串做法manacher（虽说中间插一些美刀不太美观），这里就不多讲了。
还有这题就是回文树模板题，直接查询当前加入的字符所对应的节点（即为当前前缀的最长回文后缀）长度，也是正反做一遍即可。
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=100010;
char s[N];
int z[N],ln=0;
int next[N][26],fail[N],len[N],last=0,tot;
int suf[N];
int build(int l){tot++;memset(next[tot],0,sizeof(next[tot]));len[tot]=l;return tot;
}
void init(){tot=-1;build(0),build(-1);last=ln=0;z[ln]=-1,fail[0]=1;
}
int getfail(int x){while(z[ln-len[x]-1]!=z[ln]) x=fail[x];return x;
}
void add(int c)
{c-='a';z[++ln]=c;int cur=getfail(last);if(!next[cur][c]){int now=build(len[cur]+2);fail[now]=next[getfail(fail[cur])][c];next[cur][c]=now;}last=next[cur][c];
}
int main()
{freopen("dpal.in","r",stdin);freopen("dpal.out","w",stdout);scanf("%s",s+1);int l=strlen(s+1);init();fo(i,1,l) add(s[i]),suf[i]=len[last];memset(len,0,sizeof(len));memset(fail,0,sizeof(fail));memset(z,0,sizeof(z));init();int ans=0;fd(i,l,2) add(s[i]),ans=max(ans,len[last]+suf[i-1]);printf("%d",ans);
}