  /**//*
 【題目】給你N個字符串，輸出若干個子串，滿足大于N/2個字符串含有它。
【分析】先將N個字符串并成一個字符串，中間用不同的符號分割開。
然后利用后綴數組求出Height數組，二分枚舉答案X，將Height分為若干組（如何分組？
若Height[I]大于等于X，則屬于上一組，否則屬于新的一組），
若某個組里面的后綴的來源是大于N/2個字符串的，則可行，繼續放大X，
否則縮小X。若最后X=0則No Answer，否則再次分組，輸出滿足條件的組的前綴。
 */
 #include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<string>
using namespace std;
#define maxn 100000+105
char s[maxn];
int sa[maxn],h[maxn],height[maxn],rank[maxn];
int k,n;
int maxlen;
int m;
int belong[maxn];
set<string>outset;
bool cmp1(const int & a,const int & b)
 {
return (s[a]<s[b]);
}
bool cmp2(const int & a,const int & b)
{
return (rank[a]<rank[b] || (rank[a]==rank[b]&&
(a+k<n?rank[a+k]:-1)<(b+k<n?rank[b+k]:-1)));
}
void suffixArray()
{
int i,j;
for(i=0;i<n;i++)
sa[i]=i;
sort(sa,sa+n,cmp1);
for(i=0;i<n;i++)
  {
if(i==0||s[sa[i]]!=s[sa[i-1]])
rank[sa[i]]=i;
else rank[sa[i]]=rank[sa[i-1]];
 }
for(k=1;k<n;k*=2)
{
sort(sa,sa+n,cmp2);
for(i=0;i<n;i++)
{
if( i==0 || (cmp2(sa[i],sa[i-1])||cmp2(sa[i-1],sa[i])) )
h[sa[i]]=i;
else h[sa[i]]=h[sa[i-1]];
}
memcpy(rank, h, n * sizeof(int));
}
height[0] = 0;
for(i = 0, j = 0; i < n; i++)
{
if(rank[i]>0)
{
while(s[sa[rank[i] - 1] + j] == s[i + j])
j++;
height[rank[i]] = j;
if(j > 0) j--;
}
}
}
bool ok(int len)
{
int count=0;
bool visit[105]={0};
for(int i=1;i<n;i++)
{
if(height[i]<len)
{
if(count>0)
{
count=0;
memset(visit,0,sizeof(visit));
}
}
else
{
if(!visit[belong[sa[i-1]]])
{
visit[belong[sa[i-1]]]=1;
count++;
}
if(!visit[belong[sa[i]]])
{
visit[belong[sa[i]]]=1;
count++;
}
//if(count>=ceil((double)m/2))
if(count>m/2)
return 1;
}
}
return 0;
}
int binarySearch()
{
int l=0,r=maxlen;
int mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(ok(mid))
l=mid;
else r=mid-1;
}
return l;
}
void search(int len)
{
outset.clear();
bool visit[105]={0};
int count=0;
for(int i=1;i<n;i++)
{
if(height[i]<len)
{
if(count>0)
{
if(count>m/2)
{
for(int j=0,index=sa[i-1];j<len;j++)
putchar(s[j+index]);
putchar('\n');
}
count=0;
memset(visit,0,sizeof(visit));
}
}
else
{
if(!visit[belong[sa[i-1]]])
{
visit[belong[sa[i-1]]]=1;
count++;
}
if(!visit[belong[sa[i]]])
{
visit[belong[sa[i]]]=1;
count++;
}
}
}
}
int main()
{
int tmp,j,ans;
bool first=1;
while(scanf("%d", &m)!=EOF&&m)
{
if(!first)
{
printf("\n");
}
else first=0;
n=0;
maxlen=0;
for(int i=0;i<m;i++)
{
scanf("%s",s+n);
for(j=n;s[j];j++)
belong[j]=i;
tmp=j-n;
if(tmp>maxlen)
maxlen=tmp;
n+=tmp;
s[n++]='z'+i+1;
}
//s[n]='$';
suffixArray();
ans=binarySearch();
if(!ans)
printf("?\n");
else
search(ans);
}
return 0;
}
|