文字列の袋からの補集合

文字列sが与えられた場合、文字列の袋からsの最短のスーパーシーケンスを特定する最も効率的な方法は何ですか？また、sの最後の文字は、スーパーストリングの最後の文字と一致する必要があります。文字列の袋からの補集合

'{" abbc "、" abbbbb "、" ba "}'のような文字列と '' bb ''のような文字列を持っていて、' 'abbc" 'がバッグの中で最短の "bb"のスーパーストリング？文字列を適切なデータ構造体に格納すると、 'O（| s |）'でこれを行うことができます。 –

あなたの例では、@ThomasAhleではなく、bbと出力の最後の文字が同じでなければならないので、出力は 'abbbbb'でなければなりません。 –

これで 's'は後置式でなければなりません。そして、 '{" abb "、" abba "、" aabb "、" a "}'答えは '' abb '''でしょうか？それは問題をさらに簡単にします。 –

私はそれを誤解していない限り、この問題は単純なアプローチは次のようになりP.

で最も確かである：

のと同じ文字で終わるB内のすべての文字列を取ります。この新しいバッグB 'と呼んでください。
バッグB 'のsのスーパーシーケンスであるすべての文字列を選択します。与えられた文字列sが別の文字列の部分列であるかどうかを調べるzはO（| z |）で行うことができます
以前に見つかった文字列の中で最短のものを選択してください（O（| B '|）内）

ここで| x | xの大きさを意味する。

あなたはこれらのステップを組み合わせることができますが、とにかくO（| B | * max（| z |））です。

2011-12-14 20:30:04 soulcheck

バッグ内に文字列のスーパーシーケンスがいくつかの文字で終わる文字列がない場合はどうなりますか？存在しない場合は、指数関数的に多くの文字列が存在するため、多項式時間ですべての文字列を列挙することはできません。 – templatetypedef

@templatetypedef then答えは 'such supersequence does not exist'です。 OPは、バッグ内の指定された文字列を検索しています。もし彼がそれを見つけなければ、そうである。 – soulcheck

おっと...私は質問を誤解しました！私はOPが、紐の袋があれば、袋の最短のスーパーシーケンスを見つけるよう求めていると思っていました。その問題はNP困難です。実際の問題はそれほど難しいことではありません。謝罪いたします！ – templatetypedef

バッグが頻繁に変わらないとすれば、私はDAWGを作ってA *で検索します。

2011-12-14 16:51:24 Per

sがKMPのような高速文字列検索を使用する部分文字列であるかどうかをバッグ内のすべての文字列で調べます。どのスーパーストリングが最短かチェックしてください。これはO(Σlength of strings in bag)です。

検索を複数回行う必要がある場合は、バッグ内の各文字列の接尾辞トライを作成し、これらをマージすることができます。その後、O(|s|)で検索できます。

2011-12-15 01:03:48

答えて