algorithm - n ビット文字列を見つけるための敵対的引数

Question

与えられたもの:
S、奇数個のn ビット文字列の集合
A、特定の n ビット文字列

A が S にあるかどうかを判断するアルゴリズムは、最悪の場合でも A の n ビットすべてを調べなければならないことを示してください。

もちろん、通常は文字列のすべての部分を調べてマッチングを行う必要があると予想されますが、 S のサイズが奇妙であることに特有の何かがあり、それが私を逃れています。

Answer 1

S のメンバーシップを正しく決定し、任意の入力 n ビット文字列について、文字列が S にあるかどうかを判断するアルゴリズム A があるとします。

与えられた入力 n ビット文字列 s1 について、アルゴリズム A が s1 のビット i を決して見ず、「s1 は S にある (ない) S」と言い続けるとします。次に、ビット i が反転していることを除いて s1 に等しい文字列 s2 も S に含まれます (含まれません)。つまり、A にフィードする任意の文字列について、A が特定のビットを参照しない場合、そのビットが反転された S にも (または含まれていない) 2 番目の文字列が存在します。

では、奇数サイズの集合 S の何が特別なのでしょうか? S の文字列を均等にペアにすることはできません。つまり、A が見て S にあると判断する文字列 s3 が存在する必要があり、そのため、S で別の文字列を形成するために単一のビットを反転することはできません。したがって、A は s3 のすべてのビットを調べる必要があります前に行ったように、文字列)。

Answer 2

奇数の手がかりは、でセットまたは配列の終わりを見つけることだと思いますmemory。

ビットシステムを使用していると仮定すると32、おそらくコンパイラは、メモリ内のプログラムのデータ構造を8バイト境界に揃えます。データセグメントには文字列ポインタがたくさんあります。文字列の数が奇数の場合、次に8バイトの配置が必要なものの前に4バイトのパディングがあります。文字列の数が偶数の場合、パディングはありません。

Answer 3

これを正しく理解していれば、S の弦の数が奇数か偶数かは関係ありません。S 内の特定の文字列が任意の文字列 A と一致することを確認するには、それぞれの各文字​​に対して確認する必要があります。どちらかの文字列が他の文字列よりも短い場合、またはチェックしている文字が一致しない場合は、早期に停止できます。