首页 > 代码库 > UVA-11107 Life Forms（后缀数组）
UVA-11107 Life Forms（后缀数组）
题目大意：给出n个字符串，找出所有最长的在超过一半的字符串中出现的子串。
题目分析：将所有的字符串连成一个，二分枚举长度，每次用O(n)的时间复杂度判断。连接字符串的时候中间添一个没有出现过的字符。
代码如下：
# include<iostream># include<cstdio># include<cstring># include<algorithm>using namespace std;# define mid (l+(r-l)/2)# define LL long longconst int N=100000;char s[N+105];int SA[N+105],tSA[N+105];int rk[N+105],cnt[N+105];int height[N+105];int flag[N+105];bool vis[105];int idx(char c){ return c-‘a‘;}bool same(int i,int j,int k,int n){ if(tSA[SA[i]]!=tSA[SA[j]]) return false; if(SA[i]+k>=n&&SA[j]+k>=n) return true; if(SA[i]+k<n&&SA[j]+k>=n) return false; if(SA[i]+k>=n&&SA[j]+k<n) return false; return tSA[SA[i]+k]==tSA[SA[j]+k];}void buildSA(){ int m=27; int n=strlen(s); for(int i=0;i<m;++i) cnt[i]=0; for(int i=0;i<n;++i) ++cnt[rk[i]=idx(s[i])]; for(int i=1;i<m;++i) cnt[i]+=cnt[i-1]; for(int i=n-1;i>=0;--i) SA[--cnt[rk[i]]]=i; for(int k=1;k<=n;k<<=1){ int p=0; for(int i=n-k;i<n;++i) tSA[p++]=i; for(int i=0;i<n;++i) if(SA[i]>=k) tSA[p++]=SA[i]-k; for(int i=0;i<m;++i) cnt[i]=0; for(int i=0;i<n;++i) ++cnt[rk[tSA[i]]]; for(int i=1;i<m;++i) cnt[i]+=cnt[i-1]; for(int i=n-1;i>=0;--i) SA[--cnt[rk[tSA[i]]]]=tSA[i]; swap(rk,tSA); rk[SA[0]]=0; p=1; for(int i=1;i<n;++i){ if(same(i,i-1,k,n)) rk[SA[i]]=p-1; else rk[SA[i]]=p++; } if(p>=n) break; m=p; }}void getHeight(){ int n=strlen(s); for(int i=0;i<n;++i) rk[SA[i]]=i; int k=0; for(int i=0;i<n;++i){ if(rk[i]==0) height[rk[i]]=k=0; else{ if(k) --k; int j=SA[rk[i]-1]; while(s[i+k]==s[j+k]) ++k; height[rk[i]]=k; } }}bool judge(int x,int n){ memset(vis,false,sizeof(vis)); vis[flag[SA[0]]]=true; int k=1; int len=strlen(s); for(int i=1;i<len;++i){ if(k>n) return true; if(flag[SA[i]]==-1) break; if(height[i]<x){ k=0; memset(vis,false,sizeof(vis)); } if(!vis[flag[SA[i]]]){ vis[flag[SA[i]]]=true; ++k; } } return k>n;}int f(int l,int r,int n){ ++r; while(l<r){ if(judge(mid,n)) l=mid+1; else r=mid; } return r-1;}bool ok(int i,int j){ return flag[i]==flag[j];}void print(int p,int n){ int len=strlen(s); memset(vis,false,sizeof(vis)); int k=1; vis[flag[SA[0]]]=true; for(int i=1;i<len;++i){ if(flag[SA[i]]==-1||height[i]<p){ if(k>n&&ok(SA[i-1],SA[i-1]+p-1)){ for(int j=SA[i-1];j<SA[i-1]+p;++j) printf("%c",s[j]); puts(""); } if(flag[SA[i]]==-1) break; k=0; memset(vis,false,sizeof(vis)); } if(!vis[flag[SA[i]]]){ ++k; vis[flag[SA[i]]]=true; } }}int main(){ int n; bool yy=false; while(scanf("%d",&n)&&n) { if(yy) puts(""); yy=true; if(n==1){ scanf("%s",s); printf("%s\n",s); }else{ memset(flag,-1,sizeof(flag)); s[0]=0; int high=0; for(int i=0;i<n;++i){ int m=strlen(s); scanf("%s",s+m); int nm=strlen(s); for(int j=m;j<nm;++j) flag[j]=i; s[nm]=‘z‘+1; s[nm+1]=0; high=max(nm-m,high); } buildSA(); getHeight(); int len=f(0,high,n>>1); if(len<=0) printf("?\n"); else print(len,n>>1); } } return 0;}
UVA-11107 Life Forms（后缀数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。