Algoritmo para la exclusión de los números

Question

Se le asigna un número entero N que se adapta a números enteros largos (menos de 2^63-1) y otros 50 enteros. Su tarea es encontrar cuántos números del 1 al N no contienen ninguno de los 50 números como su subcadena.

Esta pregunta es de una entrevista.

Answer 1

No especificó una base, pero supongo que será decimal sin pérdida de generalidad.

Primero, reconozca que se trata de un problema de cadena, no numérico.

Construye un autómata finito A para reconocer los 50 enteros como subcadenas de otras cadenas. Por ejemplo, los dos números enteros 44 y 3 son reconocidos como subcadenas por el RE

^.*(44|3).*$ 

Construir un finito autómata B de reconocer todos los números de menos de N. Por ejemplo, para reconocer 1 a 27 (ambos inclusive) en decimal, que se puede lograr mediante la compilación de la RE

^([1-9]|1[0-9]|2[0-7])$ 

calcular la intersección C de los autómatas A y B, que es a su vez una FA.

Utilice un algoritmo de programación dinámico para calcular el tamaño del idioma reconocido por C. Reste eso del tamaño del lenguaje reconocido por A, calculado por el mismo algoritmo.

(No estoy diciendo que esto es asintóticamente óptima, pero fue una lo suficientemente rápido para resolver un montón de problemas Proyecto Euler :)

Answer 2

esto es sólo una explicación de lo que ya larsmans escribió. Si te gusta esta respuesta, por favor véndele un voto adicional.

Un autómata finito, FA, es sólo un conjunto de estados y reglas diciendo que si se encuentra en estado S y el siguiente carácter que se alimentan es c entonces transición al estado T. Dos de los estados son especiales. Uno significa "comenzar aquí" y el otro significa "emparejé exitosamente". Uno de los personajes es especial, y significa "la cadena acaba de terminar". Entonces, toma una cuerda y un autómata finito, comienza en el estado inicial, sigue alimentando caracteres en la máquina y cambiando los estados. No puede hacer coincidir si proporciona cualquier entrada inesperada de estado. Puede lograr el emparejamiento si alguna vez alcanza el estado "Me correspondió con éxito".

Ahora existe un algoritmo bien conocido para convertir una expresión regular en un autómata finito que coincide con una cadena si y solo si esa expresión regular coincide. (Si ha leído sobre expresiones regulares, así es como funcionan los motores DFA.) Para ilustrar, usaré el patrón ^.*(44|3).*$ que significa "inicio de la cadena, cualquier cantidad de caracteres, seguido de 44 o 3, seguido de cualquier número de caracteres, seguido por el final de la cadena."

etiqueta

En primer lugar nos dejó todas las posiciones que puede estar en la expresión regular cuando estamos buscando para el siguiente carácter: ^ Un .*(4 B 4|3) C .*$

Los estados de nuestro motor de expresiones regulares serán subconjuntos de esas posiciones, y el estado especial emparejado. El resultado de una transición de estado será el conjunto de estados que podríamos alcanzar si estuviéramos en esa posición, y viéramos un carácter particular. Nuestra posición inicial es al inicio de la RE , que es {A}. Aquí están los estados a los que se puede llegar:

S1: {A} # start 
S2: {A, B} 
S3: {A, C} 
S4: {A, B, C} 
S5: matched 

Estas son las reglas de transición:

S1: 
    3: S3 
    4: S2 
    end of string: FAIL 
    any other char: S1 
S2: 
    3: S3 
    4: S3 
    end of string: FAIL 
    any other char: S1 
S3: 
    4: S4 
    end of string: S5 (match) 
    any other char: S3 
S4: 
    end of string: S5 (match) 
    any other char: S4 

Ahora bien, si usted toma cualquier cadena, principio que en el estado de S1, y seguir las reglas, igualaremos ese patrón. El proceso puede ser largo y tedioso, pero afortunadamente puede ser automatizado. Supongo que larsmans lo ha automatizado para su propio uso. (Nota técnica, la expansión de "posiciones en la RE" a "conjuntos de posiciones en las que posiblemente pueda estar" se puede hacer ya sea por adelantado, como aquí, o en tiempo de ejecución. Para la mayoría de las RE, es mejor hacerlo por adelantado , como aquí. Pero una pequeña fracción de ejemplos patológicos terminará con una gran cantidad de estados, y puede ser mejor hacerlo en tiempo de ejecución).

Podemos hacer esto con cualquier expresión regular. Por ejemplo ^([1-9]|1[0-9]|2[0-7])$ se puede obtener la etiqueta: ^ una ([1-9]|1 B [0-9]|2 C [0-7]) D $ y obtenemos los estados:

T1: {A} 
T2: {D} 
T3: {B, D} 
T4: {C, D} 

y transiciones:

T1: 
    1: T3 
    2: T4 
    3-9: T2 
    any other char: FAIL 
T2: 
    end of string: MATCH 
    any other char: FAIL 
T3: 
    0-9: T2 
    end of string: MATCH 
    any other char: FAIL 
T4: 
    0-7: T2 
    end of string: MATCH 
    any other char: FAIL 

OK, así que sabemos lo que es una expresión regular, qué autómata finito y cómo se relacionan. ¿Cuál es la intersección de dos autómatas finitos? Es solo un autómata finito que coincide cuando ambos autómatas finitos se combinan individualmente, y de lo contrario no coinciden. Es fácil de construir, su conjunto de estados es simplemente el conjunto de pares de un estado en el uno y un estado en el otro. Su regla de transición es simplemente aplicar la regla de transición para cada miembro de forma independiente, si cualquiera de las dos falla, si ambas coinciden.

Para el par anterior, vamos a ejecutar la intersección en el número 13. Comenzamos en el estado (S1, T1)

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 3 
state: (S3, T2) next char: end of string 
state: (matched, matched) -> matched 

Y luego en el número 14.

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 4 
state: (S2, T2) next char: end of string 
state: (FAIL, matched) -> FAIL 

Ahora llegamos al punto entero de esto. Teniendo en cuenta que los autómatas finitos finales, podemos utilizar la programación dinámica para averiguar cuántas cadenas hay que coincidan. Aquí es que el cálculo:

0 chars: 
    (S1, T1): 1 
    -> (S1, T3): 1 # 1 
    -> (S1, T4): 1 # 2 
    -> (S3, T2): 1 # 3 
    -> (S2, T2): 1 # 4 
    -> (S1, T2): 5 # 5-9 
1 chars: 
    (S1: T2): 5  # dead end 
    (S1, T3): 1 
    -> (S1, T2): 8 # 0-2, 5-9 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S1, T4): 1 
    -> (S1, T2): 6 # 0-2, 5-7 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S2, T2): 1  # dead end 
    (S3, T2): 1 
    -> match: 1 # end of string 
2 chars: 
    (S1, T2): 14  # dead end 
    (S2, T2): 2  # dead end 
    (S3, T2): 2 
    -> match  2 # end of string 
    match: 1 
    -> match  1 # carry through the count 
3 chars: 
    match: 3 

OK, eso es mucho trabajo, pero hemos encontrado que hay 3 cadenas que coinciden con esas dos reglas al mismo tiempo. Y lo hicimos de una manera que es automatizable y escalable a números mucho más grandes.

Por supuesto, la pregunta que nos plantearon originalmente fue cuántos coincidían con el segundo, pero no el primero. Bien, sabemos que 27 coinciden con la segunda regla, 3 coinciden con ambas, por lo que 24 deben coincidir con la segunda regla, pero no con la primera.

Como dije antes, esta es solo larsmans solution elucidated. Si aprendió algo, votale, vote por su respuesta. Si este material le parece interesante, vaya a comprar un libro como Progamming Language Pragmatics y aprenda mucho más sobre autómatas finitos, análisis sintáctico, compilación y similares. Es un muy buen conjunto de habilidades, y demasiados programadores no.