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 long const 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;
}

  

上一篇:Raspbian开启root账户


下一篇:Linux学习,path,环境变量的配置