3

バイナリ文字列で、バランス、つまり 1 と 0 の数の差が >= 0 である最長の部分文字列を見つける方法は?

例：

01110000010 -> 6: 011100

1110000011110000111 -> 19: 文字列全体

この問題は、最大値連続サブシーケンス (最大連続合計)問題と非常によく似ていますが、動的計画法の解決策は明らかではないようです。分割統治アプローチでは、どのようにマージを行うのですか? 結局、「効率的な」アルゴリズムは可能ですか? (単純な O(n^2) アルゴリズムは、考えられるすべての開始点について、すべての部分文字列を反復処理します。)

これはFinding a substring の修正版で、いくつかの条件が追加されています。違いは、リンクされた質問では、バランスがゼロを下回らない部分文字列のみが許可されることです (文字列を前方または後方の方向で見て)。与えられた問題では、後の段階で回復することを条件に、残高がゼロを下回ってもかまいません。

4

5 に答える 5

6

O(n)追加のメモリとO(n)時間が必要なソリューションがあります。

h(i)インデックスの「高さ」を次のように表しましょう

h(i) = <number of 1s in the substring 1..i> - <number of 0s in the same substring>

問題は次のように再定式i化できます。jh(i) <= h(j)j-i -> max

明らかに、h(0) = 0であり、 の場合h(n) = 0、解は文字列全体です。

}にBなるように配列を計算しましょう。B[x] = min{i: h(i) = -x言い換えると、 をB[x]左端のインデックスiにしh(i)= -xます。

配列B[x]の長さは最大nで、1 回の線形パスで計算されます。

これで、元の文字列を反復処理し、各インデックスについて、次のようiに終了する非負のバランスを持つ最長シーケンスの長さを計算できます。i

Lmax(i) = i - B[MIN{0, h(i)}]

Lmax(i)全体で最大のものでi、希望の長さが得られます。

証明は演習として残しておきます :) わからない場合は、私に連絡してください。

また、私のアルゴリズムでは元の文字列の 2 つのパスが必要ですが、それらを 1 つに折りたたむことができます。

于 2013-10-21T06:46:54.053 に答える
4

O(n)これは、0 の数に対する 1 の数を表す「高さ配列」を使用することで、非常に簡単に答えることができます。リンクされた質問の私の答えのように。

ここで、元の配列に焦点を当てるのではなく、 height によってインデックス付けされた 2 つの配列に焦点を当てます。一方には高さが見つかった最小のインデックスが含まれ、もう一方には高さが見つかった最大のインデックスが含まれます。負のインデックスは必要ないため、最小の高さが 0 になるようにすべてを上にシフトできます。

したがって、サンプル ケースの場合 (要点を示すために、最後にさらに 2 つの 1 を追加しました):

1110000011010000011111
配列の高さの視覚化
  /\
 / \
/ \
      \ /\/\ /
       \/ \ /
              \ /
               \ /
                \/
(最低の高さ = -5)
シフトされた高さ配列:
[5, 6, 7, 8, 7, 6, 5, 4, 3, 4, 5, 4, 5, 4, 3, 2, 1, 0, 1, 2, 3]
     高さ: 0 1 2 3 4 5 6 7 8
first_view = [17,16,15, 8, 7, 0, 1, 2, 3]
last_view = [17,18,19,20,21,22, 5, 4, 3]

22 個の数字と 23 個の個別のインデックス (0 ～ 22) があることに注意してください。これは、数字の間の 23 個のスペースとパディングを表します。

first_viewとlast_view配列を で構築できO(n)ます。

ここで、 の各高さについて、 のfirst_viewより大きな高さをすべてチェックしlast_view、インデックスとの差が最大のインデックスを取得するだけで済みfirst_viewます。たとえば、高さ 0 から、より大きな高さのインデックスの最大値は 22 です。したがって、インデックス 17+1 で始まる最長の部分文字列は、インデックス 22 で終了します。

配列の最大インデックスを見つけるにはlast_view、右の最大値に変換できますO(n)。

last_view_max = [22,22,22,22,22,22, 5, 4, 3]

first_viewしたがって、答えを見つけることは、単純にから減算することですlast_view_max。

first_view = [17,16,15, 8, 7, 0, 1, 2, 3]
last_view_max = [22,22,22,22,22,22, 5, 4, 3]
結果 = [ 5, 6, 7,14,15,22, 4, 2, 0]

O(n)そして、開始インデックス 0 から終了インデックス 22 まで、つまり文字列全体で達成された最大値 (再び ) を取得します。これは 22 です。=D

正当性の証明:

最大部分文字列が index で始まり、 indexiで終わるとしますj。index での高さが index での高さと同じである場合、i要件を満たすより長い部分文字列になります。したがって、各高さの最初のインデックスを考慮するだけで十分です。最後のインデックスについても同様です。k<ik..j

于 2013-10-21T07:04:47.740 に答える
0

動的計画法 -- 線形ランタイム (ついに!)

このブログ投稿に触発されました。シンプルで効率的なワンパスオンライン アルゴリズムですが、説明に時間がかかります。

考え

上記のリンクは別の問題を示しています: 最大サブシーケンス合計。元の問題の O(1) とは対照的に、ここでは O(n) の「状態」が必要です。それでも、状態は O(1) で更新できます。

問題を言い換えてみましょう。バランス0、つまりとの差1がゼロより大きい、入力内の最長の部分文字列を探しています。

状態は、私の他の分割統治ソリューションと似ています。位置ごとに、可能なバランスごとに、 positioni で終わるバランス以上の最長の文字列の開始位置を計算します。つまり、 indexで始まり で終わる文字列は残高以上であり、 で終わる文字列はなくなりました。を最大化することで結果を見つけます。 bs(i, b)bis(i, b) + 1ibii - s(i, 0)

アルゴリズム

もちろん、すべてs(i, b)をメモリに保持するわけではなく、現在のものi(入力を反復処理するもの) だけを保持します。s(0, b) := 0forb <= 0と:= undefinedforから始めb > 0ます。ごとiに、次のルールで更新します。

  1. 1が読み取られた場合: s(i, b) := s(i - 1, b - 1).
  2. 0読み取りの場合:s(i, b) := s(i - 1, b + 1)定義されてs(i, 0) := iいる場合、s(i - 1, 1)未定義の場合。

関数s( current の場合i) は、 length の配列へのポインターとして実装できます2n + 1。このポインターは、入力に応じて前後に移動します。各反復で、 の値に注意しますs(i, 0)。

それはどのように機能しますか？

sスタートから までの残高iがマイナスの場合、特にステート機能が有効になります。1まだ読み取られていない可能性のあるすべての数について、残高がゼロになる最も早い開始点が記録されます。

なぜそれが機能するのですか？

状態関数の再帰的定義は、その直接定義と同等であるため、 positionbで終了するバランス以上の最長の文字列の開始位置iです。

再帰的な定義が正しいのはなぜですか?

帰納法による証明。

于 2013-10-26T07:46:05.240 に答える
0

分割統治

もう一つの古典。O(n log n) で実行する必要がありますが、実装はかなり困難です。

考え

実行可能な最長部分文字列は、左半分または右半分にあるか、境界を越えています。両方の半分のアルゴリズムを呼び出します。境界の場合:

問題のサイズを n とします。境界を越える実行可能な最長部分文字列について、部分文字列の左半分のバランスを計算します。

-n/2 と n/2 の間の可能な各バランスについて、左半分で、境界で終わり、この (またはそれより大きい) バランスを持つ最長の文字列の長さを決定します。(線形時間!) 右半分と、境界から始まる最も長い文字列についても同じことを行います。結果は、サイズ n + 1 の 2 つの配列です。それらの1つを反転し、要素ごとに追加して最大値を見つけます。(繰り返しますが、線形です。)

なぜそれが機能するのですか？

境界を越えるバランス >= 0 の部分文字列は、他の部分がこれを補正する場合、左側または右側のいずれかの部分でバランス < 0 を持つことができます。(「借入」残高。) 重要な問題は、いくら借りるかです。すべての潜在的な「バランス クレジット」を反復処理し、最適なトレードオフを見つけます。

なぜこれは O(n log n) なのですか?

マージ (境界を越える文字列を見る) には線形時間しかかからないためです。

O(n) をマージするのはなぜですか?

演習は読者に任せます。

于 2013-10-22T23:00:40.690 に答える
0

圧縮二次ランタイム

先頭から始めて、バランスがゼロの (ローカルに) 最長の部分文字列を探します。ゼロの文字列は無視します。(コーナーケース: すべてのゼロ -> 空の文字列、残高が二度とゼロにならない -> 文字列全体。) 残高がゼロのこれらの部分文字列のうち、末尾のゼロはすべて削除されます。

B で残高 > 0 の部分文字列を示し、Z でゼロのみの部分文字列を示します。各入力文字列は、次のように分解できます (疑似正規表現表記)。

え？(ZB)* Z?

各 B は実行可能な最大のソリューションです。つまり、バランスを崩さずにどちらの方向にも拡張することはできません。ただし、崩壊後に残高がまだゼロより大きい場合は、BZB または ZBZ のシーケンスを崩壊する可能性があります。

ZBZ 部分のバランスが 0 以上の場合、BZBZB のシーケンスを単一の B に折りたたむことが常に可能であることに注意してください (線形時間で 1 回のパスで実行できます)。部分はゼロ以下です。それでも、残高がゼロを超える BZB パーツが存在する可能性はあります。残高がゼロを下回る BZBZB シーケンスでは、先頭と末尾の両方の BZB パーツの残高がゼロを超えている場合でも同様です。この時点で、どのBZBが崩壊するかを判断するのは難しそうです。

やはり二次...

とにかく、この単純化されたデータ構造を使用すると、すべての B を開始点として試すことができます (まだバランスが残っている場合は、左に拡張することもできます)。実行時間は依然として 2 次ですが、(実際には) n ははるかに小さくなっています。

于 2013-10-21T07:48:58.137 に答える