modo più veloce per bruteforzare una stringa utilizzando un carattere jolly DOS

Question

Questo problema è simile ad accecare iniezioni SQL. L'obiettivo è quello di determinare il valore esatto di una stringa, e l'unico test che si può fare è quello di vedere se un jolly in stile DOS (? = Qualsiasi carattere, * = qualsiasi numero di caratteri) si specifica si sposa con la stringa. (Quindi, in pratica si ha accesso solo a una funzione bool DoesWildcardMatch(string wildcard)).

Il modo più straight-forward è da confrontare con a*, b*, c*... fino a trovare la prima lettera, quindi ripetere. Alcune ottimizzazioni mi viene in mente:

• ricerca di *a*, *b* ecc per determinare il set di caratteri
• quando viene trovata una corrispondenza in *x*, eseguire divide-et-impera (*a*x*, *b*x*, ...)

Answer 1

Un primo pensiero. È possibile determin la lunghezza della stringa n in O(log2(n)).

• Controlla Z* dove Z rappresenta k punti interrogativi a partire da 0, 1, e poi raddoppiando il numero di punti interrogativi con ogni controllo finché non si verifica alcuna corrispondenza. k / 2 deve essere compreso tra m e O(n • log2(n))
• Trova la lunghezza esatta utilizzando lo stesso modello di cambiamento O(m) nello stesso modo in cui la ricerca binaria fa.

Conoscere la lunghezza esatta potrebbe aiutare a svolgere una sorta di divide-et-impera nel dominio spaziale.

Aggiorna

Se si conosce la lunghezza, è possibile utilizzare lo stesso modello per individuare correttamente un simbolo.

Esempio:

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

Per la lunghezza della stringa O(n • log2(n) + m) e le dimensioni alfabeto <=> Ciò richiede <=> per trovare la lunghezza della stringa, circa <=> per posizionare correttamente <=> simboli, e <=> per trovare l'usato simboli -. sommando tutti insieme rendimenti <=>

Posso immaginare che è possibile accelerare questo fondendo diversi passaggi - (? O anche più) magari test simboli usati durante la determinazione della lunghezza della stringa o simultaneamente localizzare due simboli nella prima e nella seconda metà della stringa. Ciò richiederà di ricontrollare le fasi unite in isolamento se il controllo ha esito negativo, al fine di determinare quale controllare faild. Ma finché l'assegno unito riesce, si guadagna le informazioni su entrambi.

Forse mi calcolare che domani, al fine di vedere se sarà davvero accelerare la cosa in su.

Answer 2

Per quanto riguarda il divario-et-impera, essere sicuri di tenere traccia di valore che non si noti sono presenti. Anche io non andrei con a, b, c, ma con ordine di frequenza. Una sorta di catena di Markov Da che potrebbe rendere ancora più veloce.

Una cosa da guardare fuori per è che non si può supporre che un dato letterale corrisponde sempre la stessa posizione nel input. Ciò sarà di particolare interesse per quanto riguarda la rimozione delle wild card alla fine.

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

Answer 3

Se un numero specifico di? opere, si può anche selezionare "?", "??", "???" ecc per ottenere la lunghezza della stringa, ma dubito che questo vi aiuterà molto, come si può anche verificare se hai la giusta lunghezza con un solo ulteriore controllo senza caratteri jolly dopo ogni turno.

Credo che il metodo divide con un assegno set di caratteri prima è quasi ottimale, ci sono alcuni dettagli aggiuntivi, ad esempio, se di aver aggiunto *a*b*, si dovrebbe verificare *ab* successivamente per sapere se ci sono lettere in mezzo e di Naturalmente come detto in precedenza, controllare *ab e "ab" dopo questo per sapere se hai finito sul lato destro o completamente.

Answer 4

Perché non convertire la stringa di stile jolly DOS in un'espressione regolare? per esempio:.

? Un *

diventa:

.a. *

Poi basta eseguire una semplice partita di espressione regolare il confronto che alla stringa di prova.