La forma más rápida de bruteforce una cadena con DOS comodines

Question

Este problema es similar a los ciegos de las inyecciones de SQL.El objetivo es determinar el valor exacto de una cadena, y la única prueba que puedes hacer es ver si una de las DOS estilos de caracteres comodín (?= cualquier carácter, * = cualquier número de caracteres), se debe especificar es comparable con la de la cadena.(Por lo que prácticamente sólo tiene acceso a un bool DoesWildcardMatch(string wildcard) de la función).

El sencillo forma es a prueba en contra de a*, b*, c*... hasta encontrar la primera letra, luego repita.Algunas optimizaciones puedo pensar:

• búsqueda de *a*, *b* etc.para determinar el conjunto de caracteres
• cuando un partido en *x* se encuentra, realizar divide et impera (*a*x*, *b*x*, ...)

Answer 1

Un primer pensamiento.Usted puede determinar la longitud n de la cadena en O(log2(n)).

• Verificación Z* donde Z representa k signos de interrogación comenzando con 0, 1 y, a continuación, duplicar el número de signos de interrogación con cada cheque hasta que no se produce ninguna coincidencia. n debe ser entre k / 2 y k
• Encontrar la longitud exacta utilizando el mismo patrón de cambio de k de la misma manera como binario de búsqueda.

Sabiendo que la longitud exacta podría ayudar a realizar una especie de divide et impera en el dominio espacial.

ACTUALIZACIÓN

Si conoces la longitud, se puede utilizar el mismo patrón de localizar correctamente un símbolo.

Ejemplo:

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

Para la longitud de la cadena n y el alfabeto de tamaño m esto tomará aproximadamente O(log2(n)) para encontrar la longitud de la cadena, sobre O(n • log2(n)) para colocar correctamente n los símbolos, y O(m) para encontrar los símbolos utilizados - la suma de todos los rendimientos juntos O(n • log2(n) + m).

Me imagino que es posible acelerar este proceso mediante la fusión de varios pasos - tal vez la prueba para los símbolos utilizados, mientras que la determinación de la longitud de la cadena o, simultáneamente, la ubicación de dos (o incluso más?) símbolos en la primera y segunda mitad de la cadena.Esto requerirá que vuelva a revisar la fusión de las medidas de aislamiento si la comprobación falla en el fin de determinar cual de verificación faild.Pero mientras el combinado de verificación se realiza correctamente, puede obtener información sobre ambos.

Tal vez voy a calcular que el día de mañana para ver si realmente va a la velocidad de la cosa.

Answer 2

En cuanto a la brecha-et-impera, asegúrese de mantener un registro de valor que se sabe que no está presente. También yo no iría con a, b, c, pero con orden de frecuencia. Una especie de cadena de Markov de que podría hacerlo aún más rápido.

Una cosa a tener en cuenta es que no se puede asumir que un literal dada siempre coincidirá con la misma ubicación en la entrada. Esto será de particular interés en relación con la eliminación de los comodines al final.

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

Answer 3

Si un número específico de ?las obras, también se puede comprobar "?", "??", "???" etc.para obtener la longitud de la cadena, pero dudo que esto va a ayudar mucho, como también se puede comprobar si usted tiene el derecho de longitud con un solo cheque adicional sin ningún comodín después de cada ronda.

Creo que la brecha método con un conjunto de caracteres de verificación antes es casi óptimo, hay algunos detalles adicionales, por ejemplo, si usted igualada *a*b*, usted debe comprobar *ab* después para saber si hay letras en el medio y, por supuesto, como se indicó anteriormente, compruebe *ab y "ab" después de esto para saber si has terminado en el lado derecho o en su totalidad.

Answer 4

¿Por qué no convertir su cadena de caracteres comodín estilo DOS en una expresión regular? por ejemplo:.

? A *

se convierte en:

.a. *

A continuación, sólo realizar una sencilla comparación de coincidencia de expresiones regulares que a su cadena de prueba.