Description
Link: LightOJ 1873 DNA Sequence
You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.
Time Limit: 4 second(s)
Memory Limit: 32 MB
Input
Input starts with an integer T (≤ 35), denoting the number of test cases.
Each case starts with an integer denoting the number of strings n (1 ≤ n ≤ 15) in a single line. Then these n strings (1 ≤ length ≤ 100) follow, one on each line, and they consist of the letters 'A', 'C', 'G' and 'T' only.
Output
For each case, print the case number and the shortest (and lexicographically smallest) string according to the description above.
Sample Input
2
2
TGCACA
CAT
3
TAC
ACT
CTAOutput for Sample Input
Case 1: TGCACAT
Case 2: ACTACTranslation
给你 N 个只包含 A、C、G、T 四种字符的字符串，你要找出一个最短的字符串 s，使得所有 N 个字符串都是 s 的子串。在满足 s 最短的前提下要使得 s 的字典序最小。
Analysis
状压 DP？
首先如果这些字符串有包含的情况，我们可以先直接把被包含的字符串全都去掉。
观察数据范围：$1\leqslant n\leqslant 15$，$n$ 非常小，可以考虑从状压 DP 入手。
由于题目要求我们首先答案的字符串长度最小，其次其字典序最小，我们自然想到定义 F[i][j] 表示状态为 i 并且最后一个字符串为 j 的最优字符串。
那么我们需要提前预处理一个东西：p[i][j] 表示第 i 个字符串后面接上第 j 个字符串，最长的重合串（即串 i 的后缀与串 j 的前缀的最长公共部分），例如 ABCDE 与 CDEFG 的结果是 CDE。
（在实际处理的时候，为了方便，我处理的 forp[i][j] 是第 j 个字符串去掉前面所述的“最长重合串”之后的串。即上述例子结果为 FG）
处理好这个东西就可以进行 DP 了，枚举状态转移就是在之前状态的字符串后面加上某个字符串，
内存爆炸……
但是仅仅这样是不行的，F 数组（string 类型）需要开到 f[(1<<15)][15]，而 length<=100，而且这题内存限制是 32M！
仔细思考可以发现，DP 数组不需要 F[i][j]，只需要 F[i] 即可，再开个 lst[i] 记录 i 状态的最后一个字符串编号就行了。
还是内存爆炸……
这样仍然会 MLE……（卡内存没素质）
那么接下来有两种办法：
方法之一是：注意到所有字符串里只有 4 种字符，我们可以把字符串进行压位，这样内存是可以接受，但是写起来非常麻烦（我的代码还 TLE 了……）……
方法二：仔细分析，发现我们单纯记录字符串是很盲目的，这些字符串都由那 15 个字符串拼接而来，这样记录白白多花了很多内存；其实可以把一个字符串由那些字符串拼接而成看成一个数列，那我们只要记录这个数列就可以了；
进一步发现，其实 F[i][j] 可以只记录长度，pre[i][j] 记录前驱（即 F[i][j] 这个状态是从哪里修正而来），这样只要最后进行一次搜索就可以得到整个数列。
最小字典序
这样还有个问题：怎样使得最终字符串字典序最小呢？
考虑对于一个状态 $D$，可以把所有能转移到它的状态向它建边。这样便形成了一个 DAG。所以最后只需要进行一次暴搜即可。
只要写个近两百行的状压 DP + 暴搜就可以了。
Code
留坑待补……