題目鏈接：雙倍回文

　　回文自動機第二題。構出回文自動機，那么一個回文串是一個“雙倍回文”，當且僅當代表這個串的節點\(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 500010using 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; }

轉載于:https://www.cnblogs.com/lcf-2000/p/6527173.html

總結

以上是生活随笔為你收集整理的BZOJ 2342: 【SHOI2011】 双倍回文的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。