同じ長さの 2 つの文字列間のハミング距離は、対応する位置に異なる値が存在するすべての位置の数です。次の例から理解できます:
S= "ramaniscoming"
の中国語訳は次のとおりです:S= "ramaniscoming"
T=「嫌悪感」
ここで、5 は 2 つの文字列 S と T の間のハミング距離です。これは、raman と disca が文字列の差を等しくする 2 つの単語であるためです。
###問題文###いくつかの例を通してこの問題を理解してみましょう。
入力− 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 残忍な解決策
以下は、上記のメソッドの C プログラム実装です:
リーリー ###出力### リーリー
(i-1
前回のハミング距離と現在のハミング距離の間の最小値を見つけて、最小値を保存します。
現在のハミング距離は、(K - v) 部分文字列内のゼロ要素の数と現在の S 部分文字列内のゼロの数を演算することで求められます。
最後に、全体の最小距離を返します。
以下は、上記のメソッドの C プログラム実装です。
リーリー ###出力### リーリー ###結論は###以上がK ビットのみを含む部分文字列を設定することで、バイナリ文字列のハミング距離を最小限に抑えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。