4

この一連の文字列があるとしましょう：

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

文字列が最大限に重なり合うように配置するアルゴリズムを作成するにはどうすればよいですか? それらを配置する1つの方法は次のとおりであることはすでに知っています。

qww
 www
  wwe
   wee
    eee
     eeq
      eqq
       qqq
        qqw
         qwe

ただし、上記の結果は力ずくのソリューションで見つかりました。これを行うより賢い方法はありますか？

4

1 に答える 1

4

これは最短超弦問題と呼ばれ、NP 完全です。

Jonathan Turner による論文「最短共通スーパーストリング問題の近似アルゴリズム」のアプローチに興味があるかもしれません。

于 2013-08-07T18:13:24.293 に答える