1195: [HNOI2006]最短母串

Description

给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。
Input

第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
Output

只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
Sample Input

ABCD

BCDABC
Sample Output

ABCDABC

状压DP，f[i,s]表示以i开头状态为s的情况最短字符串有多长

为了比较字典序和方便的输出最终串，我们还要记录fa[i,s]表示f[i,s]的第二个字符串是哪个

  1 var
  2     str:array[0..12,0..12]of string;
  3     g:array[0..12,0..12]of longint;
  4     f,fa:array[0..12,0..4096]of longint;
  5     a:array[0..12]of string;
  6     n:longint;
  7  
  8 function get(i,j:longint):string;
  9 var
 10     k,l:longint;
 11     flag:boolean;
 12 begin
 13     for k:=1 to length(a[i]) do
 14       begin
 15         if length(a[i])-k+1>length(a[j]) then continue;
 16         flag:=true;
 17         for l:=k to length(a[i]) do
 18           if a[i][l]<>a[j][l-k+1] then flag:=false;
 19         if flag then
 20         begin
 21           get:=a[i];
 22           for l:=length(a[i])-k+2 to length(a[j]) do
 23             get:=get+a[j][l];
 24           g[i,j]:=length(a[i])-k+1;
 25           exit(get);
 26         end;
 27       end;
 28     exit(a[i]+a[j]);
 29 end;
 30  
 31 procedure init;
 32 var
 33     i,j:longint;
 34 begin
 35     readln(n);
 36     for i:=1 to n do
 37       readln(a[i]);
 38     for i:=1 to n do
 39       for j:=1 to n do
 40         if i<>j then str[i,j]:=get(i,j);
 41 end;
 42  
 43 var
 44     d:array[0..49152,0..1]of longint;
 45  
 46 procedure work;
 47 var
 48     i,j,k,head,tail,min,lastj:longint;
 49 begin
 50     head:=1;
 51     tail:=0;
 52     for i:=1 to n do
 53       begin
 54         inc(tail);
 55         f[i,1<<(i-1)]:=length(a[i]);
 56         d[tail,0]:=i;
 57         d[tail,1]:=1<<(i-1);
 58       end;
 59     while head<=tail do
 60       begin
 61         for i:=1 to n do
 62           if d[head,1]and(1<<(i-1))=0 then
 63           begin
 64             if fa[i,d[head,1]+1<<(i-1)]=0 then
 65             begin
 66               inc(tail);
 67               d[tail,0]:=i;
 68               d[tail,1]:=d[head,1]+1<<(i-1);
 69               fa[i,d[head,1]+1<<(i-1)]:=d[head,0];
 70               f[i,d[head,1]+1<<(i-1)]:=f[d[head,0],d[head,1]]+length(a[i])-g[i,d[head,0]];
 71             end;
 72             if f[i,d[head,1]+1<<(i-1)]>f[d[head,0],d[head,1]]+length(a[i])-g[i,d[head,0]] then
 73             begin
 74               f[i,d[head,1]+1<<(i-1)]:=f[d[head,0],d[head,1]]+length(a[i])-g[i,d[head,0]];
 75               fa[i,d[head,1]+1<<(i-1)]:=d[head,0];
 76             end;
 77             if f[i,d[head,1]+1<<(i-1)]=f[d[head,0],d[head,1]]+length(a[i])-g[i,d[head,0]] then
 78             if str[i,fa[i,d[head,1]+1<<(i-1)]]>str[i,d[head,0]] then
 79             begin
 80               f[i,d[head,1]+1<<(i-1)]:=f[d[head,0],d[head,1]]+length(a[i])-g[i,d[head,0]];
 81               fa[i,d[head,1]+1<<(i-1)]:=d[head,0];
 82             end;
 83           end;
 84         inc(head);
 85       end;
 86     min:=1000;
 87     for i:=1 to n do
 88       if (f[i,1<<n-1]<min)or((f[i,1<<n-1]=min)and(str[i,fa[i,1<<n-1]]<str[j,fa[j,1<<n-1]])) then
 89       begin
 90         min:=f[i,1<<n-1];
 91         j:=i;
 92       end;
 93     write(a[j]);
 94     min:=1<<n-1;
 95     for i:=1 to n-1 do
 96       begin
 97         dec(min,1<<(j-1));
 98         lastj:=j;
 99         j:=fa[j,min+1<<(j-1)];
100         for k:=g[lastj,j]+1 to length(a[j]) do
101           write(a[j][k]);
102       end;
103 end;
104  
105 begin
106     init;
107     work;
108 end.

View Code