【国家集训队】最长双回文串
foreverlasting
2018-07-08 20:09:01
回文自动机裸题。
分别建两个回文自动机，一个是正序，一个是倒序，然后通过自动机得出最长回文长度，接着枚举切割点就好了。
2018.12.15update：之前忘记考虑不切割的情况，那只要不枚举$n$为切割点就好了。
code：
```
//2018.11.21 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline int _abs(const res &x){
return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
return x>y?x:y;
}
inline int _min(const res &x,const res &y){
return x<y?x:y;
}
const int N=1e5+10;
namespace MAIN{
int n;
int a[N],b[N];
struct PAM{
struct Pam{
int vis[26],len,fail;
}pam[N];
int las,cnt;
PAM() {pam[1].fail=pam[0].fail=1,pam[cnt=1].len=-1;}
inline void extend(const res &x,const res &id,char *str){
res p=las;
for(;str[id-pam[p].len-1]!=str[id];p=pam[p].fail);
if(!pam[p].vis[x]){
res np=++cnt,q=pam[p].fail;
for(;str[id-pam[q].len-1]!=str[id];q=pam[q].fail);
pam[np].fail=pam[q].vis[x],pam[p].vis[x]=np,pam[np].len=pam[p].len+2;
}
las=pam[p].vis[x];
}
}A,B;
char str[N];
int ans;
inline void MAIN(){
scanf("%s",str+1);
n=strlen(str+1);
for(res i=1;i<=n;i++)A.extend(str[i]-'a',i,str),a[i]=A.pam[A.las].len;
reverse(str+1,str+n+1);
for(res i=1;i<=n;i++)B.extend(str[i]-'a',i,str),b[n-i+1]=B.pam[B.las].len;
for(res i=1;i<n;i++)ans=_max(a[i]+b[i+1],ans);
printf("%d\n",ans);
}
}
int main(){
MAIN::MAIN();
return 0;
}
```