给n个字符串，求最长的多于n/2个字符串的公共子串。
依然是二分判定+height分组。
- 把这n个字符串连接，中间用不同字符隔开，跑后缀数组计算出height；
- 二分要求的子串长度，判断是否满足：height分组，统计一个组不同的字符串个数是否大于n/2；
- 最后输出方案，根据二分得出的子串长度的结果，直接再遍历一遍height，因为这儿是有序的后缀所以找到一个就直接输出。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 111000 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
int cmp(int *r,int a,int b,int l){
return r[a]==r[b] && r[a+l]==r[b+l];
}
int sa[MAXN],rank[MAXN],height[MAXN];
void SA(int *r,int n,int m){
int *x=wa,*y=wb; for(int i=; i<m; ++i) ws[i]=;
for(int i=; i<n; ++i) ++ws[x[i]=r[i]];
for(int i=; i<m; ++i) ws[i]+=ws[i-];
for(int i=n-; i>=; --i) sa[--ws[x[i]]]=i; int p=;
for(int j=; p<n; j<<=,m=p){
p=;
for(int i=n-j; i<n; ++i) y[p++]=i;
for(int i=; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j;
for(int i=; i<n; ++i) wv[i]=x[y[i]];
for(int i=; i<m; ++i) ws[i]=;
for(int i=; i<n; ++i) ++ws[wv[i]];
for(int i=; i<m; ++i) ws[i]+=ws[i-];
for(int i=n-; i>=; --i) sa[--ws[wv[i]]]=y[i];
swap(x,y); x[sa[]]=; p=;
for(int i=; i<n; ++i) x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
} for(int i=; i<n; ++i) rank[sa[i]]=i;
int k=;
for(int i=; i<n-; height[rank[i++]]=k){
if(k) --k;
for(int j=sa[rank[i]-]; r[i+k]==r[j+k]; ++k);
}
} int n,m,r[MAXN],belong[MAXN];
bool isok(int len){
int cnt=;
bool vis[]={};
for(int i=; i<=n; ++i){
if(height[i]>=len){
if(!vis[belong[sa[i]]]){
vis[belong[sa[i]]]=;
++cnt;
}
if(!vis[belong[sa[i-]]]){
vis[belong[sa[i-]]]=;
++cnt;
}
}else{
if(cnt>(m>>)) return ;
memset(vis,,sizeof(vis));
cnt=;
}
}
return ;
}
void pnt(int len){
int cnt=,idx;
bool vis[]={};
for(int i=; i<=n; ++i){
if(height[i]>=len){
idx=sa[i];
if(!vis[belong[sa[i]]]){
vis[belong[sa[i]]]=;
++cnt;
}
if(!vis[belong[sa[i-]]]){
vis[belong[sa[i-]]]=;
++cnt;
}
}else{
if(cnt>(m>>)){
for(int j=; j<len; ++j){
putchar(r[idx+j]+'a'-);
}
putchar('\n');
}
memset(vis,,sizeof(vis));
cnt=;
}
}
}
int main(){
char s[];
while(~scanf("%d",&m) && m){
n=;
for(int i=; i<m; ++i){
scanf("%s",s);
for(int j=; s[j]; ++j){
belong[n]=i;
r[n++]=s[j]-'a'+;
}
r[n++]=+i;
}
r[--n]=;
SA(r,n+,);
int l=,r=;
while(l<r){
int mid=l+r+>>;
if(isok(mid)) l=mid;
else r=mid-;
}
if(l==) puts("?");
else pnt(l);
putchar('\n');
}
return ;
}