DOS ワイルドカードを使用して文字列をブルートフォースする最速の方法

StackOverflow https://stackoverflow.com/questions/865107

質問

この問題はブラインド SQL インジェクションに似ています。目標は文字列の正確な値を決定することであり、実行できる唯一のテストは、DOS スタイルのワイルドカード (?) が使用されているかどうかを確認することです。= 任意の文字、* = 任意の数の任意の文字) は、指定した文字列と一致します。(したがって、実際にはアクセスできるのは bool DoesWildcardMatch(string wildcard) 関数）。

簡単な方法は、以下に対してテストすることです。 a*, b*, c*... 最初の文字が見つかるまで繰り返します。私が考えることができるいくつかの最適化:

  • 検索する *a*, *b* 等文字セットを決定するには
  • 試合が始まると *x* が見つかった場合は、divide-et-impera を実行します (*a*x*, *b*x*, ...)
役に立ちましたか？

解決

最初の考え。長さを決めることができます n の文字列の O(log2(n)).

  • チェック Z* どこ Z を表します k 0 から始まる疑問符、次に 1、そして一致がなくなるまでチェックするたびに疑問符の数を 2 倍にします。 n の間にある必要があります k / 2 そして k
  • 同じパターン変更を使用して正確な長さを見つけます k 二分探索と同じ方法です。

正確な長さを知ることは、空間領域で一種の分割とインペラを実行するのに役立つ可能性があります。

アップデート

長さがわかっている場合は、同じパターンを使用してシンボルを正しく見つけることができます。

例：

    ..X. ..XX (spaces added for readability)

                              + symbol may be X
                              - symbol is not X
                              X symbol is X

    *X*         => MATCH      ++++ ++++
    *X*   ????  => MATCH      ++++ ++++
    *X*?? ????  => NO MATCH   --++ ++++
    ??X?  ????  => MATCH      --X+ ++++
    ??XX  ????  => NO MATCH   --X- ++++
    ??X?  *X*?? => NO MATCH   --X- --++
    ??X?  ??X?  => MATCH      --X- --X+
    ??X?  ??XX  => MATCH      --X- --XX

文字列の長さについては n そしてアルファベットのサイズ m これには約かかります O(log2(n)) 文字列の長さを調べるには、約 O(n • log2(n)) 正しく配置する n 記号、および O(m) 使用されているシンボルを見つけるには、すべてを合計すると次のようになります。 O(n • log2(n) + m).

いくつかのステップを結合することでこれを高速化できることは想像できます。おそらく、文字列の長さを決定しながら使用されているシンボルをテストするか、文字列の前半と後半で 2 つ (またはそれ以上?) のシンボルを同時に見つけます。これには、チェックが失敗した場合に、どのチェックが失敗したかを判断するために、マージされたステップを個別に再チェックする必要があります。ただし、マージされたチェックが成功する限り、両方の情報を取得できます。

明日、それが本当にスピードアップするかどうかを確認するために計算してみます。

他のヒント

デバイド-ET-imperaについては、あなたが既知の値を追跡するために必ず存在していません。また、私はa, b, cで行くが、周波数の順序ではないと思います。それから、マルコフ連鎖のいくつかの並べ替えがさらに速くそれを作るかもしれません。

に注意することの一つは、あなたが与えられたリテラルは常に入力で同じ場所と一致すると仮定することができないということです。これは、最後にワイルドカードを取り外しに関する特定の対象としています。

c a b a
--------
* a *     match
  * b*a*  woops!

特定の数の場合は？作品は、あなたもチェックすることができ、 "？"、 "??"、 "???"などが文字列の長さを取得するために、私は、これはあなたが各ラウンドの後に任意のワイルドカードなしでただ一つの追加のチェックと右の長さを持っているならば、あなたもチェックすることができるよう多くの役立つ疑うます。

私は、文字セットのチェックで除算方式は、前にあなたが*a*b*に一致した場合たとえば、あなたが間、コースの中に文字がある場合は上記のように知って後で*ab*チェックする必要があり、いくつかの追加の詳細がありますが、ほとんど最適だと思います、あなたが右側に終了し、または完全にきたかどうかを知るために、この後*abと「AB」をチェックします。

なぜ、あなたのDOS形式のワイルドカード文字列が正規表現に変換しませんか？例えば：ます。

*？

となります：

.A。*

それからちょうどあなたのテスト文字列にそれを比較する単純な正規表現マッチを行います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top