1

A2 つの文字列とが与えられた場合、2 つの操作でBに変換Aする必要があります。B

  • delete(i, len)i: fromから始まる len 文字を削除しAます (文字は削除できません)
  • insert(i, str): 文字列 strAをi- 番目のインデックスに挿入します (空の文字列を挿入できます)

削除操作で削除される文字数を最小限に抑える必要があります。

制約:

  • 挿入は削除後にのみ適用できます
  • 削除と挿入は一度だけ適用できます

例1:

A = aabcdef  
B = aaefg

答え: delete(2, 3); insert(4, "g"). 全体として、3 文字が削除されました。これが最善の方法です。

例 2:

A = aaaaa  
B = a

4文字を削除するだけです

O(n^3)と解決策を考えO(n^2)ましたが、それよりも良い解決策があると言われました。

4

1 に答える 1

2

私は解決策を得たと思いますO(n)。それはいくつかのステップで行われます。

まず、問題を再定式化します。残っているものが等しくなるようにA、部分文字列と部分文字列を削除する必要があります。Bそして、可能な限り短い部分文字列を削除したいと考えてAいます。挿入操作は、実際には での同じ削除操作と同等であることに注意してくださいB。

レンマ。Aとの両方から同じ接頭辞または接尾辞を削除してもB、最適解には影響しません。読者に証拠を残してください:)

ここで、Aandの最大の共通サフィックスとプレフィックスを抽出します。orが空の場合は、単純な縮退ケースになります。そうでない場合は、新しい表記法,を作成しましょう。BA=XA*YB=XB*YXYA*B*A<-A*B<-B*

この時点first(A) != first(B)で、last(A) != last(B). それ以外の場合は、前のステップでプレフィックスまたはサフィックスに共通の記号を含める必要があります。

A = a1 A' a2
B = b1 B' b2

ここa1 = first(A)で、a2 = last(A)、b1 = first(B)、b2 = last(B)およびはA'およびのB'部分文字列です。ここでは、.ABa1 != b1a2 != b2

等しくするAにBは、文字列の 1 つから最初の記号を削除し、もう 1 つの文字列から最後の記号を削除する必要があります。ここには 2 つのケースがあります。Aから最初の記号を削除し、 から最後の記号を削除する 1 つだけを考えてみましょうB。

ここで行う必要があるのは、 の先頭から可能な限り少ない記号を削除してA、残った接尾辞が の接頭辞と等しくなるようにすることだけですB。そのためには、文字列のサフィックス ツリーAを構築し、すべてのプレフィックスBを調べて、それらがサフィックス ツリーに表示されているかどうかを確認する必要があります。次に、最大のものを選択します。完了すると、最大の文字列が得られますC。これは、の接尾辞Aと接頭辞ですB。

A = PC
B = CS

Pから取り外しAて完了ですS。B

オリジナルAとB（共通部分を削除していない）の場合、次のようになります。

A = XPCY
B = XCSY

問題の元の定式化では、Pが削除され、S挿入されます。

サフィックス ツリーは で構築できますO(n)。最初のステップで最も一般的な接尾辞と接頭辞を取り除くにはO(n). サフィックス ツリーのトラバーサルは で行われO(n)ます。

于 2013-04-01T07:40:26.080 に答える