bzoj 2342: [Shoi2011]双倍回文 回文树

bzoj 2342: [Shoi2011]双倍回文 回文树

题意

给一个字符串S，求S一个最长的子串T满足T的长度是4的倍数，T是回文串且T的前半部分也是回文串。
|S|<=500000

分析

先建出回文树，注意到T必然是回文树上的一个节点，且T的后半部分必然是该节点fauk树上的祖先。
那么我们就在fail树上遍历，同时记录搜索栈中每种长度的出现次数即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;const int N=500005;int n,sz,len[N],fail[N],ch[N][26],t[N],last,ans,cnt,ls[N];
char s[N];
struct edge{int to,next;}e[N];void addedge(int u,int v)
{e[++cnt].to=v;e[cnt].next=ls[u];ls[u]=cnt;
}void extend(int n,int c)
{int p=last;while (s[n-len[p]-1]!=s[n]) p=fail[p];if (!ch[p][c]){int now=++sz,k=fail[p];len[now]=len[p]+2;while (s[n-len[k]-1]!=s[n]) k=fail[k];fail[now]=ch[k][c];ch[p][c]=now;addedge(fail[now],now);}last=ch[p][c];
}void dfs(int x)
{t[len[x]]++;if (len[x]%4==0&&t[len[x]/2]) ans=max(ans,len[x]);for (int i=ls[x];i;i=e[i].next) dfs(e[i].to);t[len[x]]--;
}int main()
{scanf("%d%s",&n,s+1);sz=1;fail[0]=1;len[1]=-1;for (int i=1;i<=n;i++) extend(i,s[i]-'a');dfs(0);dfs(1);printf("%d",ans);return 0;
}