回文自动机的板子题啦
还是先胡扯几句回文自动机是如何构建的吧，这个东西比(SAM)可是简单多了
回文自动机就是一棵树，树上每一个节点表示了一个回文串，由于一个字符串本质不同的回文子串个数不会超过字符串串长，所以回文树上总结点个数是线性的
这个回文自动机由下面几个东西构成
-
(fail[x])，就是(x)这个节点的失配指针，指向(x)表示的回文串的最长回文后缀
-
(son[x][c])，就是在(x)表示的回文串左右两边加上一个字符(c)得到的回文串
-
(len[x])，就是(x)表示的回文串的长度
和(SAM)一样，回文自动机也是动态往自动机里插入一个字符
类似马拉车，我们插入(i)这个字符只会更新在(i)位置结束的最长回文子串
设(i-1)这个前缀的最长回文后缀是(f)，我们要插入的字符是(c)，如果(k)前面恰好也有一个(c)，我们就可以直接插入了
如果前面不是(c)，我们就跳一下(fail[f])看看最长的回文后缀前面是否有(c)，不然就继续跳，直到有(c)为止
设我们跳到的位置为(f)，如果(f)有(c)这个转移，说明这个回文后缀在之前已经出现过了，我们没有必要再插入了
如果没有(c)的转移，我们就需要插入一个节点了
设这个节点是(p)，显然(len[p]=len[f]+2)，因为(p)是(f)左右两边各接上一个(c)得来的
之后考虑(p)的(fail)，(fail)必须是一个真后缀，所以我们跳一下使得(k=fail[f])，之后继续跳(fail)使得(k)前面有一个(c)就好了，我们的(fail[p]=son[k][c])
最后记得更新一下当前(i)前缀的最长回文后缀是(son[f][c])
inline void ins(int c,int n) {
int f=lst;
while(S[n-len[f]-1]!=S[n]) f=fa[f];
if(!son[f][c]) {
int p=++cnt,k=fa[f];len[p]=len[f]+2;
while(S[n-len[k]-1]!=S[n]) k=fa[k];
fa[p]=son[k][c];son[f][c]=p;
}
lst=son[f][c];
}
这就是回文树插入的板子啦
实现的时候有几个小(trick)，就是这一句
len[1]=-1;fa[0]=1;cnt=1;
我们给回文树搞了两个根节点，(0)代表偶回文串，(1)表示奇回文串，我们发现(fa[0]=1)，这样我们一直匹配不上的时候就会跳到(1)，显然(S[n]+1-1=S[n])，于是我们就强行配上了
至于这道题，我们首先发现我们要求的串肯定是一个回文串，且这个回文串可以被分成(4)等份，于是(len\%4=0)
之后由于这个回文串还能被分成回文的两部分，所以这个回文串必然有一个长度为(len/2)的回文后缀
这不动物园吗
我们把(fail)树建出来，之后在上面瞎搞就好了
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
const int maxn=5e5+5;
struct E{int v,nxt;}e[maxn];
int n,lst,num,cnt,head[maxn],ans,to[maxn];
char S[maxn];
int son[maxn][26],fa[maxn],len[maxn];
inline void add(int x,int y) {
e[++num].v=y;e[num].nxt=head[x];head[x]=num;
}
inline void ins(int c,int n) {
int f=lst;
while(S[n-len[f]-1]!=S[n]) f=fa[f];
if(!son[f][c]) {
int p=++cnt,k=fa[f];len[p]=len[f]+2;
while(S[n-len[k]-1]!=S[n]) k=fa[k];
fa[p]=son[k][c];son[f][c]=p;add(fa[p],p);
}
lst=son[f][c];
}
void dfs(int x,int t) {
while(x!=t&&len[to[t]]*2<=len[x]&&to[t]!=x) t=to[t];
if(x!=t&&len[x]%4==0&&(len[t]<<1)==len[x]&&len[x]>ans) ans=len[x];
for(re int i=head[x];i;i=e[i].nxt)
to[x]=e[i].v,dfs(e[i].v,t);
}
int main() {
scanf("%d",&n);scanf("%s",S+1);
for(re int i=0;i<=n;i++) S[i]-='a';
len[1]=-1;fa[0]=1;cnt=1;add(1,0);
for(re int i=1;i<=n;i++) ins(S[i],i);
dfs(1,1);printf("%d
",ans);
return 0;
}