  /**//*
 【题目】给你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;
}
|