P4287 [SHOI2011]双倍回文
Polaris5452830
·
·
题解
关于双倍回文这道题，可以算是一道回文自动机的板子题
但是需要稍微魔改一下，在构造回文自动机的过程中顺带求出一个 trans 指针
当我们新建一个节点后，如果它的长度小于等于 2，那么这个节点的 $trans$ 指针指向它的 $fail$ 节点
否则的话，我们同理从它父亲的 $trans$ 指针指向的节点开始跳 $fail$ 指针
直到跳到某一个节点所表示的回文串的两侧都能扩展这个字符
并且拓展后的长度小于等于当前节点长度的一半
那么新建节点的 $trans$ 的指针就指向该节点的儿子
有关回文自动机的介绍及 $fail$ 指针的求法，详见[我的博客](https://www.cnblogs.com/Polaris5452830/p/10498625.html)
求完这个 $trans$ 指针之后，这个题就变得非常容易了
我们考虑一个字符串满足双倍回文
当且仅当它的 $trans$ 指针指向的节点所表示的回文串长度刚好是这个字符串长度的一半，并且这个 $trans$ 指针指向的节点所表示的回文串长度为偶数
这样我们就可以枚举每个节点，不停的更新答案
代码如下
```cpp
#include<cstdio>
#include<algorithm>
const int maxn=555555;
char s[maxn];
int cnt,last;
int trans[maxn];
int son[maxn][26];
int len[maxn],fail[maxn];
int new_node(int length)
{
len[++cnt]=length;
return cnt;
}
int get_fail(int pre,int now)
{
while(s[now-len[pre]-1]!=s[now])
pre=fail[pre];
return pre;
}
void build_PAM()
{
cnt=1,last=0;
len[0]=0,len[1]=-1;
fail[0]=1,fail[1]=1;
for(int i=1;s[i];i++)
{
int cur=get_fail(last,i);
if(!son[cur][s[i]-'a'])
{
int now=new_node(len[cur]+2);
fail[now]=son[get_fail(fail[cur],i)][s[i]-'a'];
son[cur][s[i]-'a']=now;
//顺带求出trans指针
if(len[now]<=2) trans[now]=fail[now];
else
{
int tmp=trans[cur];
while(s[i-len[tmp]-1]!=s[i]||((len[tmp]+2)<<1)>len[now]) tmp=fail[tmp];
//注意拓展后的长度为len[tmp]+2
trans[now]=son[tmp][s[i]-'a'];
}
}
last=son[cur][s[i]-'a'];
}
}
int n,ans;
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
build_PAM();
for(int i=2;i<=cnt;i++)//枚举所有节点
if(((len[trans[i]]<<1)==len[i]&&len[trans[i]]%2==0))
ans=std::max(ans,len[i]);//更新答案
printf("%d\n",ans);
return 0;
}
```