Description
给定n个字符串(S1,S2,„,Sn),要求找到一个最短的字符串T,使得这n个字符串(S1,S2,„,Sn)都是T的子串。
Input
第一行是一个正整数n(n<=12),表示给定的字符串的个数。 以下的n行,每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.Output
只有一行,为找到的最短的字符串T。在保证最短的前提下, 如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。Sample Input
2ABCD
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 }