Description
给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。
Input
第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
Output
只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
Sample Input
2
ABCD
BCDABC
Sample Output
ABCDABC
状压DP，f[i,s]表示以i开头状态为s的情况最短字符串有多长
为了比较字典序和方便的输出最终串，我们还要记录fa[i,s]表示f[i,s]的第二个字符串是哪个
var
str:array[..,..]of string;
g:array[..,..]of longint;
f,fa:array[..,..]of longint;
a:array[..]of string;
n:longint; function get(i,j:longint):string;
var
k,l:longint;
flag:boolean;
begin
for k:= to length(a[i]) do
begin
if length(a[i])-k+>length(a[j]) then continue;
flag:=true;
for l:=k to length(a[i]) do
if a[i][l]<>a[j][l-k+] then flag:=false;
if flag then
begin
get:=a[i];
for l:=length(a[i])-k+ to length(a[j]) do
get:=get+a[j][l];
g[i,j]:=length(a[i])-k+;
exit(get);
end;
end;
exit(a[i]+a[j]);
end; procedure init;
var
i,j:longint;
begin
readln(n);
for i:= to n do
readln(a[i]);
for i:= to n do
for j:= to n do
if i<>j then str[i,j]:=get(i,j);
end; var
d:array[..,..]of longint; procedure work;
var
i,j,k,head,tail,min,lastj:longint;
begin
head:=;
tail:=;
for i:= to n do
begin
inc(tail);
f[i,<<(i-)]:=length(a[i]);
d[tail,]:=i;
d[tail,]:=<<(i-);
end;
while head<=tail do
begin
for i:= to n do
if d[head,]and(<<(i-))= then
begin
if fa[i,d[head,]+<<(i-)]= then
begin
inc(tail);
d[tail,]:=i;
d[tail,]:=d[head,]+<<(i-);
fa[i,d[head,]+<<(i-)]:=d[head,];
f[i,d[head,]+<<(i-)]:=f[d[head,],d[head,]]+length(a[i])-g[i,d[head,]];
end;
if f[i,d[head,]+<<(i-)]>f[d[head,],d[head,]]+length(a[i])-g[i,d[head,]] then
begin
f[i,d[head,]+<<(i-)]:=f[d[head,],d[head,]]+length(a[i])-g[i,d[head,]];
fa[i,d[head,]+<<(i-)]:=d[head,];
end;
if f[i,d[head,]+<<(i-)]=f[d[head,],d[head,]]+length(a[i])-g[i,d[head,]] then
if str[i,fa[i,d[head,]+<<(i-)]]>str[i,d[head,]] then
begin
f[i,d[head,]+<<(i-)]:=f[d[head,],d[head,]]+length(a[i])-g[i,d[head,]];
fa[i,d[head,]+<<(i-)]:=d[head,];
end;
end;
inc(head);
end;
min:=;
for i:= to n do
if (f[i,<<n-]<min)or((f[i,<<n-]=min)and(str[i,fa[i,<<n-]]<str[j,fa[j,<<n-]])) then
begin
min:=f[i,<<n-];
j:=i;
end;
write(a[j]);
min:=<<n-;
for i:= to n- do
begin
dec(min,<<(j-));
lastj:=j;
j:=fa[j,min+<<(j-)];
for k:=g[lastj,j]+ to length(a[j]) do
write(a[j][k]);
end;
end; begin
init;
work;
end.