Si. Se puede hacer usando el algoritmo KMP en tiempo lineal. En aras de la simplicidad, explicaré el uso del algoritmo Z, que también es un algoritmo de coincidencia de cadenas de tiempo lineal.
Dada una cadena S, el algoritmo Z calculará una matriz Z donde Z [i] denota el prefijo común más largo de las cadenas S [i .. | S | – 1] y S [0 .. | S | – 1] (esa es la cadena S misma). Tenga en cuenta que también puede calcular la misma matriz Z utilizando el algoritmo KMP.
Supongamos que tenemos una matriz Z1 donde Z1 [i] denota el prefijo común más largo de las cadenas S [i .. | S | – 1] y P. Puede calcular la matriz Z1 ejecutando el algoritmo Z en P # S.
- Cómo escribir un código más limpio durante las entrevistas en el sitio
- ¿Cuál es la explicación y la prueba de la codiciosa solución en esta pregunta?
- ¿Cuáles son las ventajas de escribir código con un tiempo de ejecución mínimo?
- Cómo pasar las entrevistas de codificación para una pasantía en Facebook, Google, Microsoft, etc.
- Le dije a mi reclutador que me gustaría usar C ++ en mi entrevista técnica para un puesto de ingeniero de software general. Dado que la compañía también usa Java, ¿está bien cambiar de idioma durante la entrevista, dependiendo de la pregunta, si es más claro / más rápido para la pizarra?
Llamemos al reverso de S como S ‘ y al reverso de P como P’. Ejecute el algoritmo Z en P ‘# S’ y calcule la matriz Z2 como se indicó anteriormente .
Ahora para cada i en el rango de 0 a | S | – 1, tenemos que decir si la falta de coincidencia entre las cadenas S [i..i + | P | – 1] y P es como máximo 1. Podemos responder esto en tiempo constante usando las matrices Z1 y Z2.
Si Z1 [i] = | P | o Z1 [i] = | P | – 1, entonces hay una coincidencia.
De lo contrario, sea Z1 [i] = x. Ahora sabemos que la primera falta de coincidencia se produjo en la posición i + x. Para que la falta de coincidencia sea como máximo 1, la parte de la cadena después de i + x debe coincidir exactamente con el resto de la cadena en P. Formalmente, la cadena S [i + x + 1… i + | P | – 1] debe ser igual a P [x + 1… | P | – 1]. Puede encontrar si son iguales utilizando la matriz Z2. Puede notar que la condición es Z2 [| S | – i – | P |]> = | P | – x – 1.
Todos los índices i en los que hay coincidencia es la respuesta requerida.