首页 > 代码库 > POJ 1226后缀数组:求出现或反转后出现在每个字符串中的最长子串
POJ 1226后缀数组:求出现或反转后出现在每个字符串中的最长子串
思路:这题是论文里的最后一道练习题了,不过最后一题竟然挺水的。
因为求的是未反转或者反转后,最长公共子串。
刚开始还真不知道怎么构建连接成一个字符串,因为需要有反转嘛!
但是其实挺简单的,把未反转的和反转后的字符串都连起来,中间用未出现过的字符隔开就行了!然后未反转的和反转的在同一组。
二分枚举最长的公共前缀长度,然后统计看看这个最长的长度在不在所有的组里,如果在就符合……
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<cmath> #include<bitset> #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 11010 using namespace std; typedef long long ll; typedef unsigned long long ull; void radix(int *str,int *a,int *b,int n,int m) { static int count[maxn]; mem(count,0); for(int i=0; i<n; i++) ++count[str[a[i]]]; for(int i=1; i<=m; i++) count[i]+=count[i-1]; for(int i=n-1; i>=0; i--) b[--count[str[a[i]]]]=a[i]; } void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa { static int rank[maxn],a[maxn],b[maxn]; for(int i=0; i<n; i++) rank[i]=i; radix(str,rank,sa,n,m); rank[sa[0]]=0; for(int i=1; i<n; i++) rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]); for(int i=0; 1<<i<n; i++) { for(int j=0; j<n; j++) { a[j]=rank[j]+1; b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1; sa[j]=j; } radix(b,sa,rank,n,n); radix(a,rank,sa,n,n); rank[sa[0]]=0; for(int j=1; j<n; j++) rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]); } } void calcHeight(int *str,int *sa,int *h,int *rank,int n) //求出最长公共前缀数组h { int k=0; h[0]=0; for(int i=0; i<n; i++) rank[sa[i]]=i; for(int i=0; i<n; i++) { k=k==0?0:k-1; if(rank[i]) while(str[i+k]==str[sa[rank[i]-1]+k]) k++; else k=0; h[rank[i]]=k; } } int a[maxn],sa[maxn],height[maxn],rank[maxn]; int v[maxn],vis[110],r,n,len,j; char s[102]; bool judge(int m) { int tot=0; mem(vis,0);vis[0]=1;//隔开的字符那组直接设置已经访问过 if(!vis[v[sa[0]]]) tot++,vis[v[sa[0]]]=1; for(int i=1; i<len; i++) { if(height[i]<m) { mem(vis,0);tot=0; vis[0]=1; } if(!vis[v[sa[i]]]) tot++,vis[v[sa[i]]]=1; if(tot==n) return true; } return false; } int binary() { int ans=0,mid,l=0; while(l<=r) { mid=(l+r)>>1; if(judge(mid)) ans=mid,l=mid+1; else r=mid-1; } return ans; } int main() { //freopen("1.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d",&n); len=j=0;r=INF; for(int i=1; i<=n; i++) { scanf("%s",s); int len1=strlen(s); if(r>len1) r=len1;//二分上限 for(int k=0; k<len1; k++) a[len+k]=s[k]+150,v[len+k]=i;//v记录在哪个串中 a[len+len1]=++j;//字符串中间用没出现过的字符隔开 v[len+len1]=0; len=len+len1+1; for(int k=0; k<len1; k++) a[len+k]=s[len1-k-1]+150,v[len+k]=i;//v记录在哪个串中 a[len+len1]=++j;//字符串中间用没出现过的字符隔开 v[len+len1]=0; len=len+len1+1; } len--; suffix(a,sa,len,500); calcHeight(a,sa,height,rank,len); printf("%d\n",binary()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。