[POJ1226]Substrings（后缀数组+二分）

题目描述

传送门

题解

这题不同的地方在于要判断是否在反转后的字符串中出现。其实这并没有加大题目的难度。只需要先将每个字符串都反过来写一遍，中间用一个互不相同的且没有出现在字符串中的字符隔开，再将 n 个字符串全部连起来，中间也是用一个互不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，再将后缀分组。判断的时候，要看是否有一组后缀在每个原来的字符串或反转后的字符串中出现。

代码

#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 100005 int T,t,n,m,la,Max,ans; char a[N],s[N]; int *x,*y,X[N],Y[N],c[N],sa[N],height[N],rank[N]; int str[N],is_end[N],flag[N]; void clear() { t=n=m=la=Max=ans=0; memset(a,0,sizeof(a));memset(s,0,sizeof(s)); memset(X,0,sizeof(X));memset(Y,0,sizeof(Y));memset(c,0,sizeof(c)); memset(sa,0,sizeof(sa));memset(height,0,sizeof(height));memset(rank,0,sizeof(rank)); memset(str,0,sizeof(str));memset(is_end,0,sizeof(is_end));memset(flag,0,sizeof(flag)); } void build_sa() { m=200; x=X,y=Y; for (int i=0;i<m;++i) c[i]=0; for (int i=0;i<n;++i) ++c[x[i]=s[i]]; for (int i=1;i<m;++i) c[i]+=c[i-1]; for (int i=n-1;i>=0;--i) sa[--c[x[i]]]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (int i=n-k;i<n;++i) y[p++]=i; for (int i=0;i<n;++i) if (sa[i]>=k) y[p++]=sa[i]-k; for (int i=0;i<m;++i) c[i]=0; for (int i=0;i<n;++i) ++c[x[y[i]]]; for (int i=1;i<m;++i) c[i]+=c[i-1]; for (int i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1,x[sa[0]]=0; for (int i=1;i<n;++i) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&(sa[i-1]+k<n?y[sa[i-1]+k]:-1)==(sa[i]+k<n?y[sa[i]+k]:-1)?p-1:p++; if (p>n) break; m=p; } } void build_height() { for (int i=0;i<n;++i) rank[sa[i]]=i; int k=0;height[0]=0; for (int i=0;i<n;++i) { if (!rank[i]) continue; if (k) --k; int j=sa[rank[i]-1]; while (i+k<n&&j+k<n&&s[i+k]==s[j+k]) ++k; height[rank[i]]=k; } } bool check(int mid) { int last=t-1; bool pd=false; for (int i=t-1;i<=n;++i) { if (height[i]<mid||i==n) { int cnt=0; for (int j=last;j<i;++j) { int id=str[sa[j]]; if (id>t) id-=t; if (!flag[id]) ++cnt; ++flag[id]; } if (cnt>=t) pd=true; for (int j=last;j<i;++j) { int id=str[sa[j]]; if (id>t) id-=t; --flag[id]; } last=i; } } return pd; } int find() { int l=0,r=Max,mid,ans=0; while (l<=r) { mid=(l+r)>>1; if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } return ans; } int main() { scanf("%d\n",&T); while (T--) { clear(); scanf("%d\n",&t); for (int i=1;i<=t;++i) { gets(a);la=strlen(a); Max=max(Max,la); for (int j=0;j<la;++j) s[n++]=a[j],str[n-1]=i; s[n++]='$',str[n-1]=i; is_end[i]=n-1; for (int j=la-1;j>=0;--j) s[n++]=a[j],str[n-1]=i+t; if (i!=t) s[n++]='$',str[n-1]=i+t; is_end[i+t]=n-1; } is_end[t+t]=n; build_sa(); build_height(); for (int i=0;i<n;++i) height[i]=min(height[i],is_end[str[sa[i]]]-sa[i]); ans=find(); printf("%d\n",ans); } }