首页 > 代码库 > 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 : 图样图森破