K ビットのみを含む部分文字列を設定することで、バイナリ文字列のハミング距離を最小限に抑えます。

同じ長さの 2 つの文字列間のハミング距離は、対応する位置に異なる値が存在するすべての位置の数です。次の例から理解できます:

S= "ramaniscoming"

の中国語訳は次のとおりです:

S= "ramaniscoming"

T=「嫌悪感」

ここで、5 は 2 つの文字列 S と T の間のハミング距離です。これは、raman と disca が文字列の差を等しくする 2 つの単語であるためです。

＃＃＃問題文＃＃＃

ただし、この問題では、2 進数のみを含む 2 つの文字列間のハミング距離を見つける必要があります。 1 つの文字列 (S としましょう) と、もう 1 つの文字列 (T としましょう) がユーザーによって提供されます。最初は、その文字列には「0」ビットのみが含まれており、指定された文字列のサイズと等しいと想定します。数値「k」を取得します。その値は、部分文字列が要素として「1」のみで構成できる要素の数を表します。そのため、サイズ k の部分文字列を string(T) 内に配置します。2 つの間のハミング距離を最小化する任意の位置です。部分文字列 S と T。

いくつかの例を通してこの問題を理解してみましょう。

入力

− S = "100111" K = 5

出力

- 3

説明

- 初期文字列 T は「000000」に等しく、以下に示すように、文字列 T は文字列 S と比較して k=5 の場合の最小ハミング距離を見つけるように変更されます。 「111110」と「011111」。 100111 と 000000 の間のハミング距離は 4 です。100111 と 111110 の間のハミング距離は 3 で、100111 と 011111 の間のハミング距離も 3 です。

ただし、3 は 4 より小さいため、最小ハミング距離は 3 になります。したがって、私たちの答えは 3 です。

- S = "100101" K = 5

- 3

-初期文字列 T は「000000」に等しいため、文字列 T は文字列 S と比較するように変更され、k=5 の場合の最小ハミング距離を見つけます。次のように表示されます。 ：「111110」と「011111」。 100101 と 000000 の間のハミング距離は 3 です。100101 と 111110 の間のハミング距離は 4 で、100101 と 011111 の間のハミング距離も 4 です。

ただし、3 は 4 より小さいため、最小ハミング距離は 3 になります。したがって、私たちの答えは 3 です。

問題の説明

この問題を理解して解決策を見つけてみましょう。

解決策 1 残忍な解決策

可能なすべての文字列の中で最小のハミング距離を取得するために、異なる開始点と終了点を持つ部分文字列の位置を変更することによって文字列 T を変更します。

＃＃＃例＃＃＃

以下は、上記のメソッドの C プログラム実装です:

リーリー ＃＃＃出力＃＃＃ リーリー

ソリューション 2 最適化計画

＃＃＃アルゴリズム＃＃＃

プレフィックス合計配列を使用して 1 の数を計算し、それを最小ハミング距離として保存します

文字列 S をトラバースして、文字列 S 内の K 個の異なる部分文字列の間の値を見つけます。

• (i-1

• 前回のハミング距離と現在のハミング距離の間の最小値を見つけて、最小値を保存します。

• 現在のハミング距離は、(K - v) 部分文字列内のゼロ要素の数と現在の S 部分文字列内のゼロの数を演算することで求められます。

• 最後に、全体の最小距離を返します。

• ＃＃＃例＃＃＃

  以下は、上記のメソッドの C プログラム実装です。

  リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃
この記事では、最小ハミング距離を求めるために、まず簡単な方法を見ていきますが、時間の複雑さを改善するために、プレフィックスと配列の概念を使用します。これにより、二重カウントを回避できます。

以上がK ビットのみを含む部分文字列を設定することで、バイナリ文字列のハミング距離を最小限に抑えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。