哈哈哈广义SAM真的好简(du)单(liu)啊
到时候讲课可以拿来祸害众生，Yeah!
好了开始讲题解，我们将所有字符串加入广义SAM里面
对每一个节点维护一个bitset表示它在哪些主串中出现过，让后标记上传就用或运算就好了
因为题目要求输出方案，加上一个dfs就可以了，复杂度O(L*n/64)
（其实题目本质就是parent树上每个节点为一个集合，求一个子树的并的大小而已，金牌之王zjt给出了一种更优秀的做法，每次将具有相同元素的节点按照dfs序排好，让后在相邻两个节点的lca上面做上标记-1，标记节点操作可以在构建广义SAM的时候就可以完成，求lca可以用树剖，这样复杂度就是O(L lg L)，不过鉴于此题n<=100，上面bitset做法会更快）
当然，这道题也是SA的经典题，不过还是广义SAM比较好看~
#include<bitset>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 350010
using namespace std;
char c[N];
bitset<110> sz[N];
int s[N][26],mx[N],f[N],ans=0;
int n,m,lst=1,cnt=1,v[N],r[N];
inline int extend(int c){
int p=lst,np=lst=++cnt,q,nq;
mx[np]=mx[p]+1;
for(;p&&!s[p][c];p=f[p]) s[p][c]=np;
if(!p) return f[np]=1;
q=s[p][c];
if(mx[q]==mx[p]+1) f[np]=q;
else{
nq=++cnt;
mx[nq]=mx[p]+1;
f[nq]=f[q]; f[q]=f[np]=nq;
memcpy(s[nq],s[q],26<<2);
for(;p&&s[p][c]==q;p=f[p]) s[p][c]=nq;
}
}
inline void Ex_extend(int c){
int p=lst,q=s[p][c],nq;
if(q){
if(mx[p]+1==mx[q]) lst=q;
else{
lst=nq=++cnt;
mx[nq]=mx[p]+1;
f[nq]=f[q]; f[q]=nq;
memcpy(s[nq],s[q],26<<2);
for(;p&&s[p][c]==q;p=f[p]) s[p][c]=nq;
}
} else extend(c);
sz[lst][m]=1;
}
inline void dfs(int x,int d){
if(d!=mx[x] || d>ans) return;
if(mx[x]==ans && sz[x].count()>m){ puts(c); return; }
for(int i=0;i<26;++i)
if(s[x][i]){ c[d]=i+'a'; dfs(s[x][i],d+1); c[d]=0; }
}
inline void init(){
memset(s,0,sizeof s);
memset(f,0,sizeof f);
memset(v,0,sizeof v);
ans=0;
for(;cnt;--cnt) sz[cnt]=0;
cnt=1;
}
int _18520(){ init();
scanf("%d",&n); if(!n) return 0;
for(m=0;m<n;++m){
scanf("%s",c); lst=1;
for(int i=0,l=strlen(c);i<l;++i) Ex_extend(c[i]-'a');
} m=n>>1; memset(c,0,sizeof c);
for(int i=1;i<=cnt;++i) ++v[mx[i]];
for(int i=1;i<=cnt;++i) v[i]+=v[i-1];
for(int i=cnt;i;--i) r[v[mx[i]]--]=i;
for(int p,i=cnt;i;--i){
p=r[i]; sz[f[p]]|=sz[p];
if(sz[p].count()>m) ans=max(ans,mx[p]);
}
if(!ans) puts("?"); else dfs(1,0); puts(""); return 1;
}
int main(){ while(_18520()); }