指定されたバイナリ文字列から同じ長さの部分文字列を選択して、指定された関数を最大化します。

同じ長さの 2 つのバイナリ文字列 str1 と str2 が与えられた場合、同じ長さの値の指定された文字列から部分文字列を選択することによって、指定された関数を最大化する必要があります。与えられた関数は次のようになります -

fun(str1, str2) = (len(部分文字列))/(2^xor(sub1, sub2))。

ここで、len(substring) は最初の部分文字列の長さ、xor(sub1, sub2) は指定された部分文字列の XOR です。これらはバイナリ文字列であるため、これが可能です。

＃＃＃例＃＃＃ リーリー リーリー

イラスト

解を見つけるためにさまざまな文字列のセットを選択することもできますが、両方の文字列から「101」を選択すると、ゼロの XOR が計算され、関数は最大値を返します。

リーリー リーリー

イラスト

部分文字列として「1」を選択すると、この出力が得られます。他の文字列を選択すると、より低い値になります。

単純な方法

この方法では、すべての部分文字列を検索し、それらを比較して解決策を見つけますが、この解決策は効率的ではなく、多くの時間とスペースを必要とします。

長さ x の部分文字列を生成する平均時間計算量は N^2 で、各部分文字列の比較には N^2 の追加コストがかかります。さらに、指定された部分文字列の XOR も見つける必要がありますが、これにも N という追加の係数がかかります。つまり、上記のコードの時間計算量は N^5 となり、非常に非効率的です。

効率的な方法

＃＃＃アイデア＃＃＃

ここでのアイデアは、XOR 値が大きくなると、常に答えが減少するという単純な観察から来ています。したがって、関数の戻り値を最大化するには、XOR 値をできるだけ減らす必要があります。

両方の部分文字列がゼロの場合、達成できる最小の XOR 値はゼロです。したがって、この問題は実際には最長共通部分文字列問題から派生したものです。

XOR が 0 の場合、被除数部分は 1 となるため、最終的な答えは最大の共通部分文字列の長さになります。

＃＃＃実装＃＃＃

問題を解決するアイデアが見えてきたので、コードを実装する手順を見てみましょう -

指定された 2 つの文字列を入力として受け入れ、最終結果となる整数値を返す関数を作成します。

関数では、まず文字列の長さを取得し、次に指定された文字列を乗算したサイズの 2D ベクトルを作成します。
ネストされた for ループを使用して文字列を反復処理し、最大の共通部分文字列を取得します。
反復ごとに、2 つの文字列の現在のインデックスが一致するかどうかを確認し、2 つの文字列の最後のインデックスのベクトルから値を取得します。
それ以外の場合は、ベクトルの現在のインデックスをゼロに設定するだけです。
さらに、共通部分文字列の最大長のカウントを維持するための変数を維持します。
最後に、答えを返し、main 関数で出力します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
• 時間と空間の複雑さ

ネストされた for ループを使用し、毎回 N 回反復するため、上記のコードの時間計算量は O(N^2) です。

要素の格納に 2 次元配列を使用するため、上記のコードの空間計算量は O(N^2) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、指定されたバイナリ文字列から同じ長さの部分文字列を選択することによって、指定された関数の最大スコアを実装するコードを作成します。この単純なアプローチについてはすでに説明しましたが、非常に非効率的です。指定された関数によっては、XOR の値が小さくなるため、O(N^2) 時間計算量で最長の共通部分文字列を取得することで XOR をゼロにします。

以上が指定されたバイナリ文字列から同じ長さの部分文字列を選択して、指定された関数を最大化します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。