1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <queue>  6 #include <string>  7 #include <vector>  8 #include <cmath>  9 #include <set> 10 #define maxn 200*1000+10 11 #define maxm 2010 12 #define maxt 110 13 #define INF 0x3f3f3f3f 14 #define mod 1009 15 #define MAX_STATE 2500 16 using namespace std; 17 int n,k; 18 int N; 19 int Rank[maxn]; 20 int temp[maxn]; 21 int LCP[maxn]; 22 int SA[maxn]; 23 string T; 24 //比较(rank[k,i],rank[k,i+k])与(rank[k,j],rank[k,j+k]) 25 bool cmp_sa(int i,int j){ 26     if(Rank[i]!=Rank[j])return Rank[i]<Rank[j]; 27     else{ 28         int ri = i+k<=n?Rank[i+k]:-1; 29         int rj = j+k<=n?Rank[j+k]:-1; 30         return ri<rj; 31     } 32 } 33 //计算后缀数组O(nlognlogn) 34 void construct_sa(string S,int *sa){ 35     n = S.length(); 36     //长度为1的字符串,Rank直接取字符的编码 37     for(int i=0;i<=n;++i){ 38         sa[i]=i; 39         Rank[i]=i<n?S[i]:-1; 40     } 41     //利用对长度为k的字符串排序计算长度位2k的顺序 42     for(k=1;k<=n;k*=2){//注意这里不是 int k 43         sort(sa,sa+n+1,cmp_sa); 44         //计算新的rank，暂存到temp中 45         temp[sa[0]]=0; 46         //调整rank,相同的字符串的rank时一样的 47         for(int i=1;i<=n;++i){ 48             temp[sa[i]] = temp[sa[i-1]]+ (cmp_sa(sa[i-1],sa[i])?1:0); 49         } 50         //存回rank 51         for(int i=0;i<=n;++i){ 52             Rank[i]=temp[i]; 53         } 54     } 55 } 56 //计算LCP，O（n） 57 void construct_lcp(string S,int *sa,int *lcp){ 58     n = S.length(); 59     for(int i=0;i<=n;++i)Rank[sa[i]]=i; 60     int h=0; 61     lcp[0]=0; 62     for(int i=0;i<n;++i){ 63         //计算字符串从i位置开始的后缀及其在后缀数组前一个的后缀的LCP 64         int j = sa[Rank[i]-1]; 65         //将h先减去首字母的1的长度，保持前缀相同前提下不断增加 66         if(h>0)h--; 67         for(;j+h<n&&i+h<n;++h){ 68             if(S[j+h]!=S[i+h])break; 69         } 70         lcp[Rank[i]-1]=h; 71     } 72 } 73  74 int ID[maxn]; 75 bool judge(int len,int flag){ 76     set<int>used; 77     used.insert(ID[SA[0]]); 78     for(int i=1;i<=n;++i){ 79         while(i<n&&LCP[i-1]>=len){ 80             used.insert(ID[SA[i]]); 81             i++; 82         } 83         if(used.size()*2>N){ 84             if(flag)return true; 85             else{ 86                 for(int j=0;j<len;++j){ 87                     cout<<T[SA[i-1]+j]; 88                 } 89                 cout<<endl; 90             } 91         } 92         used.clear(); 93         used.insert(ID[SA[i]]); 94     } 95     return false; 96 } 97 void solve(int L,int R){ 98     if(!judge(1,1)){ 99         cout<<"?"<<endl;100         return;101     }102     while(L<R){103         int mid = (L+R)/2;104         if(judge(mid,1))L = mid+1;105         else R = mid;106     }107     judge(L-1,0);108 }109 int main(){110     //freopen("in.txt","r",stdin);111     //freopen("out.txt","w",stdout);112     ios::sync_with_stdio(false);113     int CASE=0;114     while(cin>>N){115         if(N==0)break;116         if(CASE!=0)cout<<endl;117         CASE++;118         string S;119         T="";120         if(N==1){121             cin>>S;122             cout<<S<<endl;123             continue;124         }125         int mmax =0;126         int cnt=0;127         for(int i=0;i<N;++i){128             cin>>S;129             int sl = S.length();130             mmax = max(mmax,sl);131             for(int j=0;j<sl;++j){132                 ID[cnt]=i;133                 cnt++;134             }135             T+=S;136             T+=‘z‘+i+1;137             cnt++;138         }139         construct_sa(T,SA);140         construct_lcp(T,SA,LCP);141         solve(1,mmax+1);142     }143 }