有一个细节不是特别懂,然后的话细节有点多,就是挺难发现的那一种,感谢大佬的博客

 然后的话,我就引用一下罗穗骞大佬和zjw大佬的分析

代码的实现

(注释版,就是解释了一下数组的意思)

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int sa[],Rank[],rsort[];
int cnt[],pos[],height[];
int a[],belong[],v[];/*因为我们中间有空格,所以的话要开到至少101000*/
/*belong数组记录属于哪一串,v数组是用来判断两个子串是否分别属于未出现过的子串*/
bool cmp(int x,int y,int k){return cnt[x]==cnt[y] && cnt[x+k]==cnt[y+k];}
char s[];
void get_sa(int n,int m)
{
int k=,p=,len;
for(int i=;i<=n;i++) Rank[i]=a[i];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[Rank[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[Rank[i]]--]=i;
for(int k=;k<n;k<<=)
{
len=;
for(int i=n-k+;i<=n;i++) pos[++len]=i;
for(int i=;i<=n;i++) if(sa[i]>k) pos[++len]=sa[i]-k;
for(int i=;i<=n;i++) cnt[i]=Rank[pos[i]];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[cnt[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[cnt[i]]--]=pos[i];
for(int i=;i<=n;i++) cnt[i]=Rank[i];
p=; Rank[sa[]]=;
for(int i=;i<=n;i++)
{
if(!cmp(sa[i],sa[i-],k)) p++;
Rank[sa[i]]=p;
}
if(p==n) break; m=p;
}
a[]=; sa[]=;
}
void get_he(int n)
{
int j,k=;
for(int i=;i<=n;i++)
{
if(Rank[i]==) continue;/*一定要这样,但是我也不知道为什么没有这个会错*/
j=sa[Rank[i]-];
if(k) k--;
while(a[j+k]==a[i+k]) k++;
height[Rank[i]]=k;
}
}
bool check(int mid,int k,int n)/*二分搜索答案*/
{
int ans=;
memset(v,,sizeof(v)); v[]=;
if(!v[belong[sa[]]]) ans++;/*没出现过*/
v[belong[sa[]]]=;
for(int i=;i<=n;i++)
{
/*分开两边来判断,只要满足条件就是好的,其实就是分组后缀,看一下哪一组满足条件*/
if(height[i]<mid)/*在左边*/
{
memset(v,,sizeof(v)); v[]=;
ans=;/*初始化一下*/
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;/*判断*/
}
else/*在右边*/
{
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;/*判断*/
}
if(ans>=k)return true;/*满足条件*/
}
return false;
}
void putt(int x,int k,int n)/*输出答案*/
{
int ans=;
memset(v,,sizeof(v)); v[]=;
if(!v[belong[sa[]]]) ans++;/*没出现过*/
v[belong[sa[]]]=;
for(int i=;i<=n;i++)
{
if(height[i]<x)/*在左边*/
{
if(ans>=k)
{
for(int j=sa[i-];j<=sa[i-]+x-;j++) printf("%c",a[j]+'a');
printf("\n");
}/*已经满足条件了就可以直接输出*/
memset(v,,sizeof(v)); v[]=;
ans=;
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;/*判断*/
}
else/*在右边*/
{
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;
}
}
if(ans>=k)/*符合条件就输出*/
{
for(int i=sa[n];i<=sa[n]+x-;i++) printf("%c",a[i]+'a');
printf("\n");
}
}
int main()
{
int t;
while(scanf("%d",&t)!=EOF && t)
{
int n=,tp=,tt=t/+;
for(int i=;i<=t;i++)
{
scanf("%s",s+);
for(int j=;j<=strlen(s+);j++)
{
a[++n]=s[j]-'a';
belong[n]=i;/*属于哪一串*/
}
a[++n]=tp; tp++;/*把二十六个字母保存到A数组里面,ascii只有127位,所以不可以直接保存*/
}
if(t==)/*只有一个的话直接输出就好了*/
{
for(int i=;i<n;i++) printf("%c",a[i]+'a');
printf("\n\n"); continue;
}
get_sa(n,); get_he(n);
int l=,r=n,ans=;
while(l<=r)/*二分找答案*/
{
int mid=(l+r)/;
if(check(mid,tt,n))
{
ans=mid;
l=mid+;
}
else r=mid-;
}
if(!ans) {printf("?\n\n"); continue;}
putt(ans,tt,n); printf("\n");
/*ans是我们最后记录的成立的那个边界范围,就是左右的边界范围*/
}
return ;
}

Tristan Code 注释版

(非注释版,挺好理解的,思路清楚了就是细节的探索咯)

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int sa[],Rank[],rsort[];
int cnt[],pos[],height[];
int a[],belong[],v[];
bool cmp(int x,int y,int k){return cnt[x]==cnt[y] && cnt[x+k]==cnt[y+k];}
char s[];
void get_sa(int n,int m)
{
int k=,p=,len;
for(int i=;i<=n;i++) Rank[i]=a[i];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[Rank[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[Rank[i]]--]=i;
for(int k=;k<n;k<<=)
{
len=;
for(int i=n-k+;i<=n;i++) pos[++len]=i;
for(int i=;i<=n;i++) if(sa[i]>k) pos[++len]=sa[i]-k;
for(int i=;i<=n;i++) cnt[i]=Rank[pos[i]];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[cnt[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[cnt[i]]--]=pos[i];
for(int i=;i<=n;i++) cnt[i]=Rank[i];
p=; Rank[sa[]]=;
for(int i=;i<=n;i++)
{
if(!cmp(sa[i],sa[i-],k)) p++;
Rank[sa[i]]=p;
}
if(p==n) break; m=p;
}
a[]=; sa[]=;
}
void get_he(int n)
{
int j,k=;
for(int i=;i<=n;i++)
{
if(Rank[i]==) continue;
j=sa[Rank[i]-];
if(k) k--;
while(a[j+k]==a[i+k]) k++;
height[Rank[i]]=k;
}
}
bool check(int mid,int k,int n)
{
int ans=;
memset(v,,sizeof(v)); v[]=;
if(!v[belong[sa[]]]) ans++;
v[belong[sa[]]]=;
for(int i=;i<=n;i++)
{
if(height[i]<mid)
{
memset(v,,sizeof(v)); v[]=;
ans=;
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;
}
else
{
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;
}
if(ans>=k)return true;
}
return false;
}
void putt(int x,int k,int n)
{
int ans=;
memset(v,,sizeof(v)); v[]=;
if(!v[belong[sa[]]]) ans++;
v[belong[sa[]]]=;
for(int i=;i<=n;i++)
{
if(height[i]<x)
{
if(ans>=k)
{
for(int j=sa[i-];j<=sa[i-]+x-;j++) printf("%c",a[j]+'a');
printf("\n");
}
memset(v,,sizeof(v)); v[]=;
ans=;
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;
}
else
{
if(!v[belong[sa[i]]]) ans++;
v[belong[sa[i]]]=;
}
}
if(ans>=k)
{
for(int i=sa[n];i<=sa[n]+x-;i++) printf("%c",a[i]+'a');
printf("\n");
}
}
int main()
{
int t;
while(scanf("%d",&t)!=EOF && t)
{
int n=,tp=,tt=t/+;
for(int i=;i<=t;i++)
{
scanf("%s",s+);
for(int j=;j<=strlen(s+);j++)
{
a[++n]=s[j]-'a';
belong[n]=i;
}
a[++n]=tp; tp++;
}
if(t==)
{
for(int i=;i<n;i++) printf("%c",a[i]+'a');
printf("\n\n"); continue;
}
get_sa(n,); get_he(n);
int l=,r=n,ans=;
while(l<=r)
{
int mid=(l+r)/;
if(check(mid,tt,n))
{
ans=mid;
l=mid+;
}
else r=mid-;
}
if(!ans) {printf("?\n\n"); continue;}
putt(ans,tt,n); printf("\n");
}
return ;
}

Tristan Code 非注释版

 /*二分搜索的时候直接记录答案*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int sa[],Rank[],rsort[];
int cnt[],pos[],h[],ans[],anslen;
int a[],belong[],v[];
bool cmp(int x,int y,int k){return cnt[x]==cnt[y] && cnt[x+k]==cnt[y+k];}
char s[];
void get_sa(int n,int m)
{
int k=,p=,len;
for(int i=;i<=n;i++) Rank[i]=a[i];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[Rank[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[Rank[i]]--]=i;
for(int k=;k<n;k<<=)
{
len=;
for(int i=n-k+;i<=n;i++) pos[++len]=i;
for(int i=;i<=n;i++) if(sa[i]>k) pos[++len]=sa[i]-k;
for(int i=;i<=n;i++) cnt[i]=Rank[pos[i]];
memset(rsort,,sizeof(rsort));
for(int i=;i<=n;i++) rsort[cnt[i]]++;
for(int i=;i<=m;i++) rsort[i]+=rsort[i-];
for(int i=n;i>=;i--) sa[rsort[cnt[i]]--]=pos[i];
for(int i=;i<=n;i++) cnt[i]=Rank[i];
p=; Rank[sa[]]=;
for(int i=;i<=n;i++)
{
if(!cmp(sa[i],sa[i-],k)) p++;
Rank[sa[i]]=p;
}
if(p==n) break; m=p;
}
a[]=; sa[]=;
}
void get_he(int n)
{
int j,k=;
for(int i=;i<=n;i++)
{
if(Rank[i]==) continue;
j=sa[Rank[i]-];
if(k) k--;
while(a[j+k]==a[i+k]) k++;
h[Rank[i]]=k;
}
}
bool check(int mid,int k,int n)
{
int sum=; bool bk=;
memset(v,,sizeof(v)); v[]=;
if(!v[belong[sa[]]]) v[belong[sa[]]]=,sum++;
for(int i=;i<=n;i++)
{
if(h[i]<mid)
{
if(sum>=k)
{
if(!bk) anslen=;
ans[++anslen]=sa[i-];bk=;
}
memset(v,,sizeof(v)); v[]=; sum=;
if(!v[belong[sa[i]]]) v[belong[sa[i]]]=,sum++;
}
else if(!v[belong[sa[i]]]) v[belong[sa[i]]]=,sum++;
}
if(sum>=k)
{
if(!bk) anslen=;
ans[++anslen]=sa[n],bk=;
}
return bk;
}
void write(int x)
{
if(!x){printf("?\n\n"); return ;}
for(int i=;i<=anslen;i++)
{
for(int j=ans[i];j<=ans[i]+x-;j++) printf("%c",a[j]+'a');
printf("\n");
}
printf("\n");
}
int main()
{
int t;
while(scanf("%d",&t)!=EOF && t)
{
int n=,tp=,tt=t/+;
for(int i=;i<=t;i++)
{
scanf("%s",s+);
for(int j=;j<=strlen(s+);j++)
{
a[++n]=s[j]-'a';
belong[n]=i;
}
a[++n]=tp; tp++;
}
if(t==)
{
for(int i=;i<n;i++) printf("%c",a[i]+'a');
printf("\n\n"); continue;
}
get_sa(n,); get_he(n);
int l=,r=n,ans=;
while(l<=r)
{
int mid=(l+r)/;
if(check(mid,tt,n))
{
ans=mid;
l=mid+;
}
else r=mid-;
}
write(ans);
}
return ;
}

常数较小,较快 Code

05-22 04:25
查看更多