1

長さの異なる 2 つの文字列 S1 と S2 が与えられた場合、S1 の最後の文字が一致する S1 と S2 の両方の等しいサブシーケンスの数を見つけるための効率的な方法は何ですか。

例えば）

S1 = ayb

S2 = axbxxb

この場合、2 つの等しいサブシーケンスが存在します。

 "b"  => S1[2],S2[2]
 "b"  => S1[2],S2[5]
 "ab" => S1[0],S2[0] and S1[2],S2[2]
 "ab" => S1[0],S2[0] and S1[2],S2[5]

これは動的プログラミングを使用して解決できることを知っています。誰かがこの問題に効率的にアプローチするためのアイデアを提供してくれれば幸いです。

4

1 に答える 1

0

これは基本的に正規表現の一致の問題です。

まず、「最後の文字が一致する」条件を取り除きましょう。この問題を「条件のない単純な数の等しい部分列の問題」に減らしたいと考えています。

S1="a 1 a 2 ...a n Z" とします。S1'="a 1 a 2 ...a n "とする。さらに、S2 に Z が N 回出現するとします。出現ごとに書くことができます

S2 に Z が N 回出現するとします。各出現iに対して、 S2 i = "b 1 b 2 ...b k i Zb k i +1 ..." と書くことができます。S2'="b 1 b 2 ...b k i "とします。ここで、1..N の各 i について、S1' と S2' iの簡単な問題を解きます。

では、単純な問題をどのように解決すればよいでしょうか。

短い方の弦を S1 とします。では書いてみましょう"abc…t"。に変換し".*a?.*b?.*…t?.*"ます。これが正規表現です。ここで、正規表現が S2 と一致する方法がいくつあるかを数えます。一致は、NFA ベースのアルゴリズムで実行できます。

実際に一致数をカウントするには、NFA ベースの一致アルゴリズムの内部動作を理解する必要があります。任意の時点でアクティブな一連の状態があります。状態は 2 つに分割することも、2 つの状態を結合することもできます。間違った文字に遭遇すると、状態が死ぬ可能性があります。したがって、初期状態にスコア 1 を割り当てます。状態が分割されると、それぞれの新しい状態は親のスコアを継承します。2 つの州が合併すると、新しい州がスコアの合計を取得します。州が死ぬと、そのスコアが下がります。

これが、あなたが動的計画法のアプローチと呼んでいるものと何か違うかどうかはわかりません。最大 2 Nの一致があるため、一部の入力ではこれに時間がかかります。

更新:「最後の文字の一致」の問題を単純な問題に還元することなく、直接解決することも可能であるように思われます。S2 に Z が 2 回出現するとします: S2="ab…pZq…yZ"。(とにかく、最後の Z の後のすべての文字を無視できます)。S2: から正規表現を構築できます".*a?.*b?.*…p?.*(Z|Z?.*q?.*…y?.*Z)"。より多くのオカレンスが同じ方法で処理されます。一見冗長な正規表現は、正しい数の一致を維持するために必要です (一致があるという事実だけではありません)。

于 2012-04-11T10:37:35.297 に答える