[HNOI2006]最短母串问题 (ac

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


  首先要想到n!的做法,就是枚举每个串放的位置的全排列,对每个排列以此加起来,然后比较答案 发现有很多重叠的问题,因此考虑状压,f[i][s] 表示最后一个选的串是第i个串,当前所选串的集合为s 然后进行dp(我不会),嘿嘿。   一看多串,ac自动鸡,然后..........e..... 想一下多串匹配的过程是,就是从根节点一直跳,那我们就按照这个来就完了,每一个点都向下一个子节点跳就完事了,用f[i][j] 表示当前到达的编号为i的节点,当前已经包含的串的集合是j。 然后就bfs,从大到小遍历儿子保证字典序最小,bfs本身保证了长度最短。

   
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 610
 5 #define ac 4596
 6 #define inf 2139062143
 7 
 8 int n, m, maxn, tmp, head, tail;
 9 int f[AC][ac], q1[AC * ac], q2[AC * ac];
10 short l1[AC][ac], l2[AC][ac];
11 int c[AC][26], val[AC], fail[AC], go[AC], tot;
12 char s[AC];
13 
14 inline void add()
15 {
16     int len = strlen(s + 1), now = 0;
17     for(R i = 1; i <= len; i ++)
18     {
19         int v = s[i] - 'A';
20         if(!c[now][v]) c[now][v] = ++ tot, go[tot] = v;
21         now = c[now][v];
22     }
23     val[now] |= tmp, tmp <<= 1;
24 }
25 
26 #define q q1
27 void build()
28 {
29     for(R i = 0; i < 26; i ++)
30         if(c[0][i]) q[++ tail] = c[0][i];
31     while(head < tail)
32     {
33         int x = q[++ head];
34         for(R i = 0; i < 26; i ++)
35         {
36             if(c[x][i]) fail[c[x][i]] = c[fail[x]][i], q[++ tail] = c[x][i];
37             else c[x][i] = c[fail[x]][i];
38         }
39     }    
40     for(R i = 1; i <= tot; i ++) val[i] |= val[fail[i]];
41 }
42 #undef q 
43 
44 void pre()
45 {
46     scanf("%d", &n);
47     maxn = (1 << n) - 1, tmp = 1;
48     memset(f, 127, sizeof(f));
49     for(R i = 1; i <= n; i ++) scanf("%s", s + 1), add();
50 }
51 
52 void bfs()
53 {
54     head = tail = 0;
55     q1[++ tail] = 0, q2[tail] = 0;
56     f[0][0] = 0;
57     while(head < tail)
58     {
59         int x = q1[++ head], sta = q2[head];
60         if(sta == maxn)
61         {
62             head = 0;
63             while(x) 
64             {
65                 q1[++ head] = go[x];
66                 int tmp1 = x, tmp2 = sta;
67                 x = l1[tmp1][tmp2], sta = l2[tmp1][tmp2];
68             }
69             for(R i = head; i; i --) printf("%c", q1[i] + 'A');
70             return ;
71         }
72         for(R i = 0; i < 26; i ++)
73         {
74             int v = c[x][i], w = sta | val[v];
75             if(f[v][w] == inf) 
76             {
77                 q1[++ tail] = v, q2[tail] = w;
78                 f[v][w] = f[x][sta] + 1;
79                 l1[v][w] = x, l2[v][w] = sta;
80             }
81         }
82     }
83 }
84 
85 int main()
86 {
87
88     pre();
89     build();
90     bfs();
91 
92     return 0;
93 }

 

           
上一篇:BZOJ1192: [HNOI2006]鬼谷子的钱袋


下一篇:bzoj 1197: [HNOI2006]花仙子的魔法