为最大重叠排列字符串

Question

假设我有一组字符串：

strings = {'qqq', 'eqq', 'qqw', 'www', 'qww', 'wwe', 'eee', 'eeq', 'wee', 'qwe'}

这样的字符串是怎样排列的？我已经知道一种安排方式是：

^{pr2}$

然而，我找到了一个暴力解决方案上面的结果。有更聪明的方法吗？在

Answer 1

这被称为最短超弦问题，是NP完全问题。在

您可能对论文Approximation Algorithms for the Shortest Common Superstring Problem by Jonathan Turner中的方法感兴趣。在