包含一组中出现次数最多的字符串的最短字符串

我有一个多项式时间算法，我懒得编写代码。但我会为您描述。

首先，使集合中的每个字符串加上空字符串成为图的节点。空字符串彼此连接，反之亦然。如果一个字符串的结尾与另一个字符串的开头重叠，它们也将连接。如果两个可以重叠的量不同，则它们将具有多个边缘。（因此，它并非完全是图形...）

每条边都有成本和价值。该费用是你有多少个字符来扩展你是从旧的结束移动到新的终端建设的字符串。（换句话说，第二个字符串的长度减去重叠的长度。）该值是您完成了多少个新字符串，它们越过前者和后者之间的障碍。

您的示例为{“ ab”，“ bd”，“ abd”，“ babd”，“ abc”}。这是(cost, value)每个转换的对。

 from  ->   to  : (value, cost)
 ""    ->   "ab": (    1,    2)
 ""    ->   "bd": (    1,    2)
 ""    ->  "abd": (    3,    3) # we added "ab", "bd" and "abd"
 ""    -> "babd": (    4,    4) # we get "ab", "bd", "abd" and "babd"
 ""    ->  "abc": (    2,    3) # we get "ab" and "abc"
 "ab"  ->     "": (    0,    0)
 "ab"  ->   "bd": (    2,    1) # we added "abd" and "bd" for 1 character
 "ab"  ->  "abd": (    2,    1) # ditto
 "ab"  ->  "abc": (    1,    1) # we only added "abc"
 "bd"  ->     "": (    0,    0) # only empty, nothing else starts "bd"
"abd"  ->     "": (    0,    0) 

“ babd”->“”：（0，0）“ babd”->“ abd”：（0，0）＃重叠，但未添加任何内容。“ abc”->“”：（0，0）

好的，所有这些都已设置。我们为什么要这张图？

请注意，如果我们以成本为0且值为0的“”开始，则采用遍历该图的路径，该路径构成一个字符串。它正确说明了成本，并提供了一个下限。该值可以更高。例如，如果您的集合是{“ ab”，“ bc”，“ cd”，“ abcd”}，则路径“”->“ ab”->“ bc”->“ cd”将导致字符串“ abcd” ”的成本为4，预测值为3。但是，该价值估算缺少我们匹配“ abcd”的事实。

但是，对于仅由集合中的子字符串组成的任何给定字符串，都有一条通过图的路径，该路径具有正确的成本和正确的值。（在每个选择中，您都希望选择尚未计数的最早的起始匹配字符串，而其中选择最长的匹配字符串。这样您就永远不会错过任何匹配项。）

因此，我们已将问题从构造字符串转变为通过图形构造路径。我们要做的是建立以下数据结构：

for each (value, node) combination:
    (best cost, previous node, previous value)

填充该数据结构是一个动态编程问题。一旦填写完毕，我们就可以追溯到它，以找到图中的哪条路径以该成本使我们达到了该值。在此路径下，我们可以找出执行此操作的字符串。

有多快？如果我们的集合中有K字符串，那么我们只需要填写K * N值，就可以为每个值提供最多的K新值候选。这使得寻找O(K^2 * N)问题的道路。