最短母串问题题解

思路

如果一个输入字符串已经是另一个输入字符串的子串，那么只要覆盖较长字符串就一定会覆盖它，因此可以先删除重复字符串和被其他字符串包含的字符串。

对于剩余字符串，设一个排列表示它们依次加入母串的顺序。当前母串以字符串 $A$ 结尾，下一字符串为 $B$ 时，应取 $A$ 的后缀与 $B$ 的前缀能够相等的最大长度，只追加 $B$ 未被覆盖的部分。小规模可以枚举所有排列。

满分范围用子集动态规划同时枚举所有排列。状态记录已经使用的字符串集合和最后一个字符串；状态值保存该状态能够得到的最短母串，在长度相同时保留字典序最小者。

做法

预处理任意两个保留字符串之间的最大后缀与前缀重合长度。令状态 $(M,i)$ 表示集合 $M$ 中的字符串都已经加入，且当前母串以第 $i$ 个字符串结尾。初始状态只包含一个字符串。

从 $(M,i)$ 转移到尚未使用的字符串 $j$ 时，在当前字符串后追加 $S_j$ 去掉重合前缀后的剩余部分，得到 $(M\cup\{j\},j)$ 的候选。先比较总长度，再比较完整字符串的字典序。最终在包含全部字符串的所有结尾状态中用同一规则选出答案。

正确性证明

删除被包含字符串不会改变合法母串集合。对于任意固定排列，每次采用相邻字符串的最大后缀前缀重合不会破坏已经出现的字符串，并且使该排列得到的母串最短。

状态 $(M,i)$ 的后续可选转移只由集合 $M$ 和结尾字符串 $i$ 决定。若两个候选处于同一状态，较短者在追加相同后续内容后仍不会更长；长度相同时，字典序较小者追加相同后续内容后仍然更小。因此每个状态只保留长度最短、再取字典序最小的候选不会丢失全局最优解。动态规划枚举了所有保留字符串的排列，所以最终答案既是最短母串，也是所有最短母串中字典序最小者。

复杂度

设删除包含关系后剩余 $m$ 个字符串，答案长度至多为 $L$。预处理重合长度的时间复杂度为 $O(m^2L)$，动态规划有 $O(2^m m)$ 个状态和 $O(2^m m^2)$ 次转移；计入字符串比较与复制，时间复杂度为 $O(2^m m^2L)$，空间复杂度为 $O(2^m mL)$。