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

Stack Overflow用户

提问于 2012-07-21 00:44:49

回答 1查看 245关注 0票数 1

我正在尝试寻找一种算法，它通过一个单词列表，给出前缀和后缀的最小列表，使得每个单词都是前缀和后缀的串联。

例如：

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

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

这有可能吗？

回答已采纳

发布于 2012-07-21 07:39:28

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

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

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

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

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11583649

复制

相似问题

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