获取lis前缀后缀最小列表的算法or和python实现

Question

我试图找到一个算法，在一个单词列表中，给出前缀和后缀的最小列表，使得每个单词都是前缀和后缀的集合。在

例如：

[banano, ananas, applenas, appleno, neo, neas]

=> [bana,anan,e, apple] [as no]

有可能吗？在

Answer 1

解决方案的定义不是唯一的。例如，对于语言[aa，ab，bb]，解决方案可能是[a，b][a，b]，或者是[aa，ab，bb]和空字符串。在

这个问题可以理解为最小字符串覆盖问题的一个实例（假设每个字符串以一个强制的开始字符串字符开头，以另一个强制的结束字符串字符结束。允许的覆盖字典将由输入语言中所有单词的所有前缀和后缀组成。在

一般的字符串覆盖问题是NP难的，但是一旦您施加了一个规则（在这里由开始字符串和结束字符串字符的出现所暗示的），即只有固定的最大数量的字符串（这里是两个）可以覆盖任何给定的输入字符串，它就变成了polynomially solvable。在

这里是一个最小字符串覆盖问题的solver的C++实现。在