#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<memory>
#include<vector>
using namespace std;
#define MAXN 500000
#define INF 2100000000
int sa[MAXN],rank[MAXN],lrank[MAXN],height[MAXN];
void SuffixArray();
void GetLCP();
bool judge(int);
int T,n,belong[MAXN];
char s[MAXN];
void chkmin(int& a,int b){if(a>b)a=b;}
vector<int> V;
int main(){
    while(scanf("%d",&T),T){
        n=0;
        gets(s);
        int mx=INF,i,j;
        for(i=0;i<T;++i){
            gets(s+n);
            for(j=n;s[j];++j)belong[j]=i;
            chkmin(mx,j-n);
            s[n=j]='z'+1+i;
            belong[n++]=i;
        }
        SuffixArray();
        GetLCP();
        int l=0,r=mx,mid;
        while(l<r){
            mid=(l+r+1)/2;
            if(judge(mid))l=mid;
            else r=mid-1;
        }
        judge(l);
        if(l==0)puts("?");
        else{
            for(i=0;i<V.size();++i){
                for(j=0;j<l;++j)putchar(s[V[i]+j]);putchar(10);
            }
        }
        putchar(10);
    }
    return 0;
}
bool vis[1010];
bool judge(int X){
    memset(vis,0,sizeof(bool)*T);
    int cont=0;
    V.clear();
    for(int i=0;i<n;++i){
        if(height[i]<X){
            if(cont>0){
                if(cont>T/2){
                    V.push_back(sa[i]);
                }
                memset(vis,0,sizeof(bool)*T);
                cont=0;
            }
        }else{
            if(!vis[belong[sa[i]]])vis[belong[sa[i]]]=true,++cont;
            if(!vis[belong[sa[i+1]]])vis[belong[sa[i+1]]]=true,++cont;
        }
    }
    return V.size();
}
bool _SA1(int a,int b){
    return s[a]<s[b]||s[a]==s[b]&&a<b;
}
int K;
bool _SA2(int a,int b){
    return rank[a]<rank[b]||rank[a]==rank[b]&&rank[a+K]<rank[b+K];
}

void SuffixArray(){
    int i;
    for(i=0;i<n;++i)sa[i]=i;
    sort(sa,sa+n,_SA1);
    for(rank[sa[0]]=0,i=1;i<n;++i){
        rank[sa[i]]=rank[sa[i-1]];
        if(s[sa[i]]!=s[sa[i-1]])++rank[sa[i]];
    }
    for(K=1;K<n&&rank[n-1]<n-1;K<<=1){
        sort(sa,sa+n,_SA2);
        for(i=0;i<n;++i)lrank[i]=rank[i];
        for(rank[sa[0]]=0,i=1;i<n;++i){
            rank[sa[i]]=rank[sa[i-1]];
            if(lrank[sa[i]]!=lrank[sa[i-1]]||lrank[sa[i]+K]!=lrank[sa[i-1]+K])rank[sa[i]]++;
        }
    }
}
void GetLCP(){
    int i,j,dt;
    for(i=dt=0;i<n;++i){
        if(rank[i]==n-1)height[rank[i]]=dt=0;
        else{
            if(dt>0)--dt;
            for(j=sa[rank[i]+1];s[i+dt]==s[j+dt];++dt);
            height[rank[i]]=dt;
        }
    }
}
/*
aaaaa  ->aaaa
asd  -> ?
asddasd -> asd
*/
这样的结果也ac？

• 知道了n！=1 (0) cycpp 2009-08-18 20:53:31