python - 获取列表前缀后缀的最小列表的算法或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 难的，但是一旦你强加规则（这里由开始字符串和结束字符串字符的出现暗示），只有固定的最大数量的字符串（这里是两个）可以覆盖任何给定输入字符串，它变成多项式可解的。

这是最小字符串覆盖问题求解器的C++ 实现。