怎么没有正常的后缀数组二分的题解啊
给定 \(n\) 个字符串，求出最长的，在多于 \(\left\lfloor\frac{n}{2}\right\rfloor\) 个字符串中出现的子串，并按照字典序从小到大输出。
\(n \leq 100\)，\(|S| \leq 1000\)，根据套路可以将所有字符串连成一个，不同的字符串用特殊符号隔开，然后建出新串的 SA 和 height 数组。
显然 \(L\) 满足可二分性，因为如果某个字符串符合条件，那么它的子串也必然符合条件。故可以二分 \(L\) ，转化为一个存在性问题。
将排序后的后缀分组，每一组里面任意两个字符串的 LCP \(\geq L\) 。当这一组里面出现了来自 \(> \left\lfloor\frac{n}{2}\right\rfloor\) 个字符串的后缀，说明存在满足条件且长度为 \(L\) 的字符串。
最后还要输出答案。因为后缀排序后所有后缀都按照字典序排好了，所以从前往后枚举每一组，组内字符串满足条件直接输出就好了。
时间复杂度 \(O(n \log{n})\) 。注意要特判 \(n = 1\) 的情况。多测要清空，以及记得每组样例之间空行。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int M=2e5+10;
char str[M],S[M];
char ch[5]={'?','!','&','^','$'};
int n,len,L[110],R[110],bel[M];
int x[M],y[M],sa[M],buc[M],ht[M];
void SA(){
int tot=127;
for(int i=1;i<=len;i++) buc[x[i]=str[i]]++;
for(int i=2;i<=tot;i++) buc[i]+=buc[i-1];
for(int i=len;i>=1;i--) sa[buc[x[i]]--]=i;
for(int k=1;k<=len;k<<=1){
int cur=0;
for(int i=len-k+1;i<=len;i++) y[++cur]=i;
for(int i=1;i<=len;i++)
if(sa[i]>k) y[++cur]=sa[i]-k;
for(int i=1;i<=tot;i++) buc[i]=0;
for(int i=1;i<=len;i++) buc[x[i]]++;
for(int i=2;i<=tot;i++) buc[i]+=buc[i-1];
for(int i=len;i>=1;i--) sa[buc[x[y[i]]]--]=y[i];
std::swap(x,y),x[sa[1]]=cur=1;
for(int i=2;i<=len;i++)
if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=cur;
else x[sa[i]]=++cur;
if(cur==len) break;
tot=cur;
}
}
void getheight(){
for(int i=1,cur=0;i<=len;i++){
if(x[i]==0) continue;
if(cur) cur--;
while(str[cur+i]==str[cur+sa[x[i]-1]]) cur++;
ht[x[i]]=cur;
}
}
int cnt[110];
bool check(int l){
for(int i=1;i<=len;){
for(int j=1;j<=n;j++) cnt[j]=0;
int cur=i,qwq=0;
while(cur<len && ht[cur+1]>=l) cur++;
for(int j=i;j<=cur;j++) cnt[bel[j]]++;
for(int j=1;j<=n;j++) qwq+=(bool)cnt[j];
if(qwq>n/2) return true;
i=cur+1;
}
return false;
}
void printresult(int l){
for(int i=1;i<=len;){
for(int j=1;j<=n;j++) cnt[j]=0;
int cur=i,qwq=0;
while(cur<len && ht[cur+1]>=l) cur++;
for(int j=i;j<=cur;j++) cnt[bel[j]]++;
for(int j=1;j<=n;j++) qwq+=(bool)cnt[j];
if(qwq>n/2){
int st=sa[i];
for(int k=st;k<=st+l-1;k++) putchar(str[k]);
putchar('\n');
}
i=cur+1;
}
}
void clear(){
len=0;
memset(str,0,sizeof str);
memset(L,0,sizeof L);
memset(R,0,sizeof R);
memset(bel,0,sizeof bel);
memset(x,0,sizeof x);
memset(y,0,sizeof y);
memset(buc,0,sizeof buc);
memset(sa,0,sizeof sa);
memset(ht,0,sizeof ht);
}
int Case;
int main(){
while(~scanf("%d",&n) && n){
if((++Case)!=1) putchar('\n');
clear();
int l=0,r=0,ans=0;
for(int i=1;i<=n;i++){
scanf(" %s",S+1);
int t=strlen(S+1); r=std::max(r,t);
L[i]=++len;
for(int j=1;j<=t;j++,len++) str[len]=S[j];
str[R[i]=len]=ch[i%5];
}
if(n==1){
for(int i=1;i<len;i++) putchar(str[i]);
putchar('\n'),putchar('\n');
continue;
}
SA(),getheight();
for(int i=1;i<=n;i++)
for(int j=L[i];j<=R[i];j++) bel[x[j]]=i;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
if(!ans) printf("?\n");
else printresult(ans);
}
return 0;
}