python - 排列字符串以获得最大重叠

Question

假设我有这组字符串：

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

如何编写一个算法来排列字符串以使它们最大程度地重叠？我已经知道安排它们的一种方法如下：

qww
 www
  wwe
   wee
    eee
     eeq
      eqq
       qqq
        qqw
         qwe

但是，我通过蛮力解决方案找到了上述结果。有没有更聪明的方法来做到这一点？

Answer 1

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

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