给定(n)个串，求在一半以上的串中出现过的最长公共子串
对(n)个串建广义后缀自动机，用树状数组统计(parent)树上每个节点子树包含的串的个数，之后遍历一遍求出最长公共子串长度，并标记相应节点，之后根据长度和标记在(DAG)上(dfs)即可
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
typedef long long ll;
const int Maxn=200010;
vector<int>g[Maxn];
struct Q{
int id,l,r;
}ask[Maxn];
int n;
struct Suffix_Automata{
int maxlen[Maxn], trans[Maxn][26], link[Maxn], Size;
vector<int>sz[Maxn];
void clr(int x){
maxlen[x]=link[x]=0;
memset(trans[x],0,sizeof(trans[x]));
sz[x].clear();
}
void init(){
Size=1;
clr(1);
}
inline int insert(int ch, int last,int id){
if (trans[last][ch]){
int p = last, x = trans[p][ch];
if (maxlen[p] + 1 == maxlen[x]) {sz[x].push_back(id);return x;}
else{
int y = ++Size;
clr(y);
maxlen[y] = maxlen[p] + 1;
for (int i = 0; i < 26; ++i)
trans[y][i] = trans[x][i];
while (p && trans[p][ch] == x)
trans[p][ch] = y, p = link[p];
link[y] = link[x], link[x] = y;
sz[y].push_back(id);
return y;
}
}
int z = ++Size, p = last;
clr(z);
sz[z].push_back(id);
maxlen[z] = maxlen[last] + 1;
while (p && !trans[p][ch])
trans[p][ch] = z, p = link[p];
if (!p) link[z] = 1;
else{
int x = trans[p][ch];
if (maxlen[p] + 1 == maxlen[x]) link[z] = x;
else{
int y = ++Size;
clr(y);
maxlen[y] = maxlen[p] + 1;
for (int i = 0; i < 26; ++i)
trans[y][i] = trans[x][i];
while (p && trans[p][ch] == x)
trans[p][ch] = y, p = link[p];
link[y] = link[x], link[z] = link[x] = y;
}
}
return z;
}
int pre[Maxn],c[Maxn],vis[Maxn];
void solve_init(){
for(int i=0;i<=Size+1;i++)g[i].clear(),pre[i]=c[i]=vis[i]=0;;
for(int i=2;i<=Size;i++)g[link[i]].push_back(i);
}
int in[Maxn],out[Maxn],num[Maxn],tim;
void getdfn(int x,int fa){
in[x]=++tim;
num[tim]=x;
for(int i=0;i<g[x].size();i++){
if(g[x][i]==fa)continue;
getdfn(g[x][i],x);
}
out[x]=tim;
ask[x]={x,in[x],out[x]};
}
int ans[Maxn];
void add(int x,int y){
for(int i=x;i<=Size;i+=i&(-i))
c[i]+=y;
}
int sum(int x){
int ans=0;
for(int i=x;i;i-=i&(-i))
ans+=c[i];
return ans;
}
int mx;
char str[Maxn];
void dfs(int x,int length){
if(length==mx){
if(vis[x]){
str[length]=' ';
puts(str);
}
return ;
}
for(int i=0;i<26;i++){
if(trans[x][i]){
str[length]='a'+i;
dfs(trans[x][i],length+1);
}
}
}
static bool cmp(Q x,Q y){return x.r < y.r;}
void solve(){
solve_init();
tim=0;
getdfn(1,-1);
sort(ask+1,ask+1+Size,cmp);
int now=1;
for(int i=1;i<=Size;i++){
for(int j=0;j<sz[num[i]].size();j++){
if(pre[sz[num[i]][j]])
add(pre[sz[num[i]][j]],-1);
add(i,1);
pre[sz[num[i]][j]]=i;
}
while(now<=Size&&ask[now].r==i){
ans[ask[now].id]=sum(i)-sum(ask[now].l-1);
++now;
}
}
mx=0;
for(int i=2;i<=Size;i++){
if(ans[i]>n/2){
mx=max(mx,maxlen[i]);
}
}
for(int i=2;i<=Size;i++){
if(ans[i]>n/2&&maxlen[i]==mx){
vis[i]=1;
}
}
if(mx==0)puts("?");
else dfs(1,0);
puts("");
}
}sam;
char s[Maxn];
int main(){
while(scanf("%d",&n)&&n){
sam.init();
for(int i=0;i<n;i++){
scanf("%s",s);
int last=1;
for(int j=0;s[j];j++)
last=sam.insert(s[j]-'a',last,i);
}
sam.solve();
}
return 0;
}