【题意】
n个字符串，求最长的出现在多于一半字符串中的子串
【输入】
多组数据
每组第一行一个n表示n个字符串
接下来n行是n个字符串
【输出】
对于每组答案，输出最长的出现在多于一半字符串中的子串，如有多个，按字典序输出
若不存在，则输出'?'
两组数据答案之间用空行分隔
后缀数组经典运用之一
二分答案，然后按height分组，看每组来自多少个不同的字符串
注意n=1的情况
program poj3294;
var
n,m,i,j,k,tot,ans,s,e,mid,limit,max:longint;
ok:boolean;
root,temp:ansistring;
belong,change,total,dl,now,keep,rank,sa,height:array [-1..110001] of longint;
yes:array [0..1001] of boolean;
fin:array [0..1001] of longint;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while root[dl[i]]<root[k] do inc(i);
while root[dl[j]]>root[k] do dec(j);
if i>j then break;
swap(dl[i],dl[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
function search (mid:longint):boolean;
begin
search:=false;
tot:=0;
fillchar(yes,sizeof(yes),false);
k:=1;
yes[belong[sa[m+1]]]:=true;
for i:=m+2 to n do
begin
if (height[i]<mid)or(fin[belong[sa[i]]]-sa[i]<mid) then
begin
if k>=limit then
begin
search:=true;
inc(tot);
dl[tot]:=sa[i-1];
end;
k:=1;
fillchar(yes,sizeof(yes),false);
yes[belong[sa[i]]]:=true;
continue;
end;
if not yes[belong[sa[i]]] then
begin
yes[belong[sa[i]]]:=true;
inc(k);
end;
end;
if k>=limit then
begin
search:=true;
inc(tot);
dl[tot]:=sa[i-1];
end;
end;
begin
repeat
readln(m);
if m=0 then break;
if m and 1 = 1 then limit:=m-m div 2
else limit:=m div 2 + 1;
root:='';
max:=maxlongint;
for i:=1 to m do
begin
readln(temp);
if length(temp)<max then max:=length(temp);
root:=root+temp+' ';
end;
if m=1 then
begin
writeln(temp);
writeln;
continue;
end;
n:=length(root);
for i:=1 to n do
dl[i]:=i;
qsort(1,n);
k:=1;
for i:=1 to n do
begin
if root[dl[i]]<>root[dl[k]] then k:=i;
rank[dl[i]]:=k;
end;
k:=0;
while 1 shl k<n do
begin
for i:=1 to n do
if i+(1 shl k)>n then change[i]:=0
else change[i]:=rank[i+(1 shl k)];
fillchar(total,sizeof(total),0);
for i:=1 to n do
inc(total[change[i]]);
for i:=1 to n do
total[i]:=total[i]+total[i-1];
for i:=1 to n do
begin
dl[total[change[i]-1]+1]:=i;
inc(total[change[i]-1]);
end;
fillchar(total,sizeof(total),0);
for i:=1 to n do
inc(total[rank[i]]);
for i:=2 to n do
total[i]:=total[i]+total[i-1];
fillchar(now,sizeof(now),0);
fillchar(keep,sizeof(keep),0);
for i:=1 to n do
begin
if now[rank[dl[i]]]<>change[dl[i]] then
begin
now[rank[dl[i]]]:=change[dl[i]];
total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]];
keep[rank[dl[i]]]:=0;
end;
inc(keep[rank[dl[i]]]);
rank[dl[i]]:=total[rank[dl[i]]-1]+1;
end;
inc(k);
end;
for i:=1 to n do
sa[rank[i]]:=i;
fillchar(height,sizeof(height),0);
for i:=1 to n do
begin
if rank[i]=1 then continue;
k:=height[rank[i-1]]-1;
if k<0 then k:=0;
while (i+k<=n)and(sa[rank[i]-1]+k<=n)
and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k);
height[rank[i]]:=k;
end;
k:=1;
for i:=1 to n do
if root[i]=' ' then
begin
fin[k]:=i;
inc(k);
end
else belong[i]:=k;
s:=0;
e:=max;
while s<>e do
begin
mid:=s+e-(s+e) div 2;
if search(mid) then s:=mid
else e:=mid-1;
end;
if s=0 then
begin
writeln('?');
writeln;
continue;
end;
ok:=search(s);
for i:=1 to tot do
writeln(copy(root,dl[i],s));
writeln;
until false;
end.