题意
给你 \(N\) 个由小写字母组成的字符串 \(S_1, S_2, \ldots, S_N\)，找出一个母串使得它包含所有这些字符串作为它的子串，最小化该母串的长度并输出。
\(1 \leq N \leq 20\)，\(\sum |S_i| \leq 2 \times 10 ^ 5\)
（没错洛谷翻译就是我写的）
思路
首先如果有一个字符串被另一个字符串完全包括，那么直接把被包括的字符串删了显然是不影响答案的。
对于剩下的字符串，直接把所有字符串拼接在一起形成母串肯定可行，但假如我们有两个字符串，前一个字符串的后缀和后一个的字符串前缀有一段匹配，那么将后一个字符串的这段前缀删去再加入显然也是合法的母串，所以我们可以贪心删最长匹配。
我们设 \(l_i\) 为第 \(i\) 为 \(S_i\) 的长度，\(d(i, j)\) 为第 \(j\) 个字符串拼接在第 \(i\) 个字符串后面时最少需要额外追加的字符数量，按照刚才的思路 \(d(i, j)\) 就等于 \(l_j\) 减去 \(S_i\) 的后缀与 \(S_j\) 的前缀的最长匹配。那么该如何计算这个最长匹配呢？当然可以使用 exkmp。对于每对 \((i, j)\)，因为最长匹配长度 \(\leq \min(l_i, l_j)\)，所以直接枚举最长匹配可能的取值再用哈希判断复杂度就对了，\(O(n^2 + n \sum l_i)\)。
现在问题就被转换成了如果 \(S_i\) 成为母串开头的字符串，那么母串会增加 \(l_i\) 长度。如果 \(S_j\) 要接在 \(S_i\) 后面，母串最少会增加 \(d(i, j)\) 长度。还是问你母串最短能是多少。
那直接把每个字符串看成一个点，\(d(i, j)\) 看成 \(i\) --> \(j\) 的一条边的边权，从第 \(i\) 个点出发初始有 \(l_i\) 的代价，那么经过所有点恰好一次的通路的最小代价就是母串的最短长度。不难发现实际上就是经典的 TSP 问题，状压 dp 解决之。这部分时间复杂度为 \(O(n^2 \times 2^n)\)，所以总复杂度就是 \(O(n^2 + n \sum l_i + n^2 \times 2^n)\)，5 秒非常宽松，
标签：匹配,int,题解,leq,母串,字符串,abc343G,hashy From： https://www.cnblogs.com/SkyWave20100601/p/18052371