DOSワイルドカードを使用して文字列をbruteforceする最速の方法

Question

この問題は、ブラインドSQLインジェクションに似ています。目標は文字列の正確な値を決定することです。DOSスタイルのワイルドカード（？=任意の文字、* =任意の数の任意の文字）が文字列と一致するかどうかを確認するだけです。 （実際にはbool DoesWildcardMatch(string wildcard)機能にしかアクセスできません）。

最初の文字が見つかるまでa*, b*, c*...をテストしてから、繰り返します。私は考えることができるいくつかの最適化：

• など*a*, *b*の検索文字を決定する*x*上の一致が見つかったとき
• を設定し、除算-ET-imperaを行う（*a*x*, *b*x*, ...）

Answer 1

最初に考えました。文字列の長さnをO(log2(n))に設定できます。 Zが、その後、0と1を起動して、一致が発生しなくなるまで、すべてのチェックに疑問符の数を2倍k疑問符を表し

• チェックZ*。 nはバイナリ検索が行うのと同じ方法でkを変え、同じパターンを使用して正確な長さを探す
k/2間と kでなければなりません。

正確な長さを知ることは、空間領域である種のdivide-et-imperaを実行するのに役立ちます。

UPDATE

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

例：文字列の長さnとアルファベットサイズmについては

 
    ..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 

この程度O(n • log2(n))が正しくnシンボルを配置するために、そしてO(m)が使用するシンボルを見つけるために、文字列の長さを見つけるために約O(log2(n))がかかります - 一緒に合計すると、O(n • log2(n) + m)が得られます。

いくつかのステップをマージすることでこれをスピードアップすることができます - 文字列の長さを決定したり、同時に文字列の最初と後半に2つ。これは、チェックが失敗した場合、どのチェックが失敗したかを判断するために、マージされたステップを単独で再チェックする必要があります。しかし、マージされたチェックが成功する限り、両方の情報が得られます。

多分私はそれが実際に物事をスピードアップするかどうかを見るために明日計算します。

Answer 2

の場合特定の数？ "？"、 "??"、 "???"をチェックすることもできます。等の文字列の長さを取得するが、私はあなたも、各ラウンドの後にワイルドカードなしで1つの追加のチェックだけで正しい長さを持っているかどうかを確認することができますこれは多くの助けになるのだろうか。

私は文字セットチェックの分割方法が最も最適であると思います。例えば、*a*b*と一致した場合は、*ab*をチェックしてから間に文字があるかどうかを確認してください上記の場合は、*abと「ab」をチェックして、右側で完了したか完全に完了したかを確認してください。

Answer 3

DOSスタイルのワイルドカード文字列を正規表現に変換してみませんか？例えば：

*

は次のようになります？。

.A *

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

Answer 4

divide-et-imperaについては、あなたが知っている値がないことを必ず確認してください。また、私はa, b, cと一緒に行くつもりはないが、周波数の順序で。それからのマルコフ連鎖のいくつかの並べ替えは、それをより速くするかもしれません。

注意しなければならないことは、与えられたリテラルが常に入力内の同じ場所に一致するとは想定できないことです。これは最後にワイルドカードを取り除くことに特に関心があります。

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