首页 > 代码库 > BZOJ 2342: 【SHOI2011】 双倍回文
BZOJ 2342: 【SHOI2011】 双倍回文
题目链接:双倍回文
回文自动机第二题。构出回文自动机,那么一个回文串是一个“双倍回文”,当且仅当代表这个串的节点\(u\)顺着\(fail\)指针往上跳,可以找到一个节点\(x\)满足\(2len_x=len_u\)。当然还需要\(len_u\)是\(4\)的倍数。
然后我们把\(fail\)树构出来,在上面\(dfs\)一遍就做完了。
下面贴代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 500010 using namespace std; typedef long long llg; char a[maxn]; int l[maxn],s[maxn][26],f[maxn]; int head[maxn],next[maxn],to[maxn]; int tt,la,ans,dt; bool w[maxn]; void add(int c,int n){ int p=la; while(a[n-l[p]-1]!=a[n]) p=f[p]; if(!s[p][c]){ int np=++tt,k=f[p]; l[np]=l[p]+2; while(a[n-l[k]-1]!=a[n]) k=f[k]; f[np]=s[k][c]; s[p][c]=np; } la=s[p][c]; } void link(int x,int y){to[++dt]=y;next[dt]=head[x];head[x]=dt;} void dfs(int u){ if(~l[u]&1) w[l[u]]=1; if(l[u]%4==0 && w[l[u]>>1]) ans=max(ans,l[u]); for(int i=head[u];i;i=next[i]) dfs(to[i]); w[l[u]]=0; } int main(){ File("a"); l[++tt]=-1; f[0]=1; int n;scanf("%d %s",&n,a+1); for(int i=1;i<=n;i++) add(a[i]-‘a‘,i); for(int i=tt;i>1;i--) link(f[i],i); dfs(1); dfs(0); printf("%d",ans); return 0; }
BZOJ 2342: 【SHOI2011】 双倍回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。