首页 > 代码库 > BZOJ3654 : 图样图森破
BZOJ3654 : 图样图森破
考虑枚举回文中心,然后向两边扩展,当匹配到当前串的边界的时候,枚举下一个串接上。
这个过程可以通过记忆化搜索来完成,设:
$f[i][0]$表示对于$i$这个位置,$[i,串结尾]$等待匹配的最长回文子串。
$f[i][1]$表示对于$i$这个位置,$[串开头,i]$等待匹配的最长回文子串。
如果在转移的过程中发现两个串都已经匹配到了边界,或者转移有环,那么说明答案无限。
用后缀数组支持lcp的询问,时间复杂度$O(nL+L\log L)$。
#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int N=400010,M=105;int n,m,i,j,k,x,y,st[M],en[M],from[N],f[N][2],v[N][2],vis[N][2],ans;char a[N],s[N];namespace SA{int n,rk[N],sa[N],height[N],tmp[N],cnt[N],Log[N],f[18][N];char s[N];void build(int n,int m){ int i,j,k;n++; for(i=0;i<n;i++)cnt[rk[i]=s[i]]++; for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; for(i=0;i<n;i++)sa[--cnt[rk[i]]]=i; for(k=1;k<=n;k<<=1){ for(i=0;i<n;i++){ j=sa[i]-k; if(j<0)j+=n; tmp[cnt[rk[j]]++]=j; } sa[tmp[cnt[0]=0]]=j=0; for(i=1;i<n;i++){ if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])cnt[++j]=i; sa[tmp[i]]=j; } memcpy(rk,sa,n*sizeof(int)); memcpy(sa,tmp,n*sizeof(int)); if(j>=n-1)break; } for(j=rk[height[i=k=0]=0];i<n-1;i++,k++) while(~k&&s[i]!=s[sa[j-1]+k])height[j]=k--,j=rk[sa[j]+1]; for(i=2;i<n;i++)Log[i]=Log[i>>1]+1; for(i=1;i<n;i++)f[0][i]=height[i]; for(j=1;j<18;j++)for(i=1;i+(1<<j)-1<n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);}inline int ask(int x,int y){ int k=Log[y-x+1]; return min(f[k][x],f[k][y-(1<<k)+1]);}inline int lcp(int x,int y){ if(x==y)return N; x=rk[x],y=rk[y]; if(x>y)swap(x,y); return ask(x+1,y);}}inline int query(int x,int y){ return min(SA::lcp(x,m-1-y),min(en[from[x]]-x,y-st[from[y]])+1);}void getinf(){ puts("Infinity"); exit(0);}int dfs(int u,int p){ if(vis[u][p])getinf(); if(v[u][p])return f[u][p]; v[u][p]=vis[u][p]=1; int&ret=f[u][p]; if(!p){ for(int i=1;i<=n;i++){ int k=query(u,en[i]); int x=u+k-1,y=en[i]-k+1; if(x<en[from[u]]&&y>st[i])ret=max(ret,k*2); else if(x==en[from[u]]&&y==st[i])getinf(); else if(x==en[from[u]])ret=max(ret,k*2+dfs(y-1,1)); else ret=max(ret,k*2+dfs(x+1,0)); } }else{ for(int i=1;i<=n;i++){ int k=query(st[i],u); int x=u-k+1,y=st[i]+k-1; if(x>st[from[u]]&&y<en[i])ret=max(ret,k*2); else if(x==st[from[u]]&&y==en[i])getinf(); else if(x==st[from[u]])ret=max(ret,k*2+dfs(y+1,0)); else ret=max(ret,k*2+dfs(x-1,1)); } } vis[u][p]=0; return ret;}int main(){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%s",a); st[i]=m; for(j=0;a[j];j++)from[m]=i,s[m++]=a[j]; en[i]=m-1; } m<<=1; for(i=0,j=m-1;i<j;i++,j--)s[j]=s[i],from[j]=from[i]; for(SA::n=m,i=0;i<m;i++)SA::s[i]=s[i]; SA::build(m,128); for(i=1;i<=n;i++)ans=max(ans,max(dfs(st[i],0),dfs(en[i],1))); for(i=1;i<=n;i++){ for(j=st[i];j<=en[i];j++){ k=query(j,j); x=j-k+1,y=j+k-1; if(x>st[i]&&y<en[i])ans=max(ans,k*2-1); else if(x==st[i]&&y==en[i])getinf(); else if(x==st[i])ans=max(ans,k*2-1+dfs(y+1,0)); else ans=max(ans,k*2-1+dfs(x-1,1)); } for(j=st[i];j<en[i];j++){ k=query(j+1,j); x=j-k+1,y=j+k; if(x>st[i]&&y<en[i])ans=max(ans,k*2); else if(x==st[i]&&y==en[i])getinf(); else if(x==st[i])ans=max(ans,k*2+dfs(y+1,0)); else ans=max(ans,k*2+dfs(x-1,1)); } } return printf("%d",ans),0;}
BZOJ3654 : 图样图森破
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。