算法或python实现获取列表的前缀后缀的最小列表

Question

我试图找到一个算法，与一个单词列表，给出最小的前缀和后缀列表，使每个单词是concatanation一个前缀和一个后缀。

例如：

[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-hard，但只要您强加规则（此处暗示了begin-string和end-string的出现字符），只有固定的最大数量的字符串（这里是两个）可以覆盖任何给定的输入字符串，它变成polynomially solvable。

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