鉴于子序列的集合从字符串

Given a collection of sub-sequences from a string.

例如：

abc
acd
bcd

现在的问题是，如何确定这些序列的最短字符串？

The problem is, how to determine the shortest string from these sequences?

对于上面的例子，最短的字符串 ABCD 。

For the above example, the shortest string is abcd.

下面的的子序列的表示字符串的一部分，但不一定是连续的。如 ACD 是字符串的一个子序列 ABCD 。

Here sub-sequences means part of a string but not necessarily consecutive. like acd is a sub-sequence of string abcd.

修改的：这个问题实际上来自项目欧拉问题79 ，在这个问题，我们有50个子序列，每个具有3的长度和所有字符是数字。

Edit: This problem actually comes from Project Euler problem 79, in that problem, we have 50 subsequences, each has the length of 3. and all characters are digits.

推荐答案

这个问题是很好的研究和创造最短常见的超层

This problem is well studied and coined "Shortest common supersequence"

有关两个字符串，它是在为O（n）。假设n是串的最大长度。 O（n）被用于构建 后缀阵列 ，然后为O（n）解决在最长公共子的问题。

For two strings, it is in O(n). Suppose n is the maximum length of string. O(n) is used to build the suffix array and then O(n) to solve the Longest Common Subsequence problem.

对于两个以上的字符串，它是NP完全问题。

For more than two strings, it is NP-Complete.