Il modo più veloce per forzare una stringa usando un carattere jolly DOS

Question

Questo problema è simile alle iniezioni SQL cieche. L'obiettivo è determinare il valore esatto di una stringa, e l'unico test che puoi fare è vedere se un carattere jolly in stile DOS (? = Qualsiasi carattere, * = qualsiasi numero di caratteri) specificato viene abbinato alla stringa. (Quindi praticamente hai solo accesso a una funzione bool DoesWildcardMatch(string wildcard)).

Il modo semplice è di testare a*, b*, c*... fino a trovare la prima lettera, quindi ripetere. Alcune ottimizzazioni mi viene in mente:

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

Answer 1

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

• check 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. n deve essere compreso tra k/2 e k
• Trova la lunghezza esatta utilizzando lo stesso modello modificando k nello stesso modo della ricerca binaria.

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

UPDATE

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 n e alfabeto stringa di formato m questo richiederà circa O(log2(n)) per trovare la lunghezza della stringa, circa O(n • log2(n)) per posizionare correttamente n simboli, e O(m) per trovare i simboli usati - sommando tutti insieme produce O(n • log2(n) + m).

Posso immaginare che sia possibile accelerare unendo diversi passaggi, magari testare i simboli usati mentre si determina la lunghezza della stringa o contemporaneamente localizzare due (o anche più?) Simboli nella prima e nella seconda metà della stringa . Ciò richiederà di ricontrollare i passaggi uniti separatamente se il controllo fallisce al fine di determinare quale controllo fallire. Ma finché il controllo unito riesce, ottieni informazioni su entrambi.

Forse lo calcolerò domani per vedere se accelera davvero la cosa.

Answer 2

Se un numero specifico di? funziona, puoi anche controllare "?", "??", "???" ecc. per ottenere la lunghezza della corda, ma dubito che ciò sarà di grande aiuto in quanto puoi anche controllare se hai la lunghezza giusta con un solo controllo aggiuntivo senza caratteri jolly dopo ogni round.

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

Answer 3

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

un *

diventa:

.a *

Poi basta eseguire una semplice partita di espressione regolare a confronto che, per la stringa di prova..

Answer 4

Per quanto riguarda il divide-et-impera, assicurarsi di tenere traccia del valore che si conosce non sono presenti. Inoltre non andrei con a, b, c, ma con ordine di frequenza. Una sorta di catena del markov potrebbe renderlo ancora più veloce.

Una cosa a cui prestare attenzione è che non si può presumere che un dato letterale corrisponderà sempre alla stessa posizione nell'input. Questo sarà di particolare interesse per quanto riguarda la rimozione delle jolly alla fine.

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