Knuth-Morris y Pratt introducen un algoritmo de tiempo lineal para el problema de coincidencia de cadenas. Se logra un tiempo de coincidencia de O (n) evitando la comparación con un elemento de 'S' que haya estado involucrado previamente en comparación con algún elemento del patrón 'p' a emparejar. es decir, nunca se retrocede en la cadena 'S'
Componentes del algoritmo KMP:
1. La función de prefijo (Π): La función de prefijo, Π para un patrón, encapsula el conocimiento sobre cómo el patrón coincide con el cambio de sí mismo. Esta información se puede utilizar para evitar un cambio inútil del patrón 'p'. En otras palabras, esto permite evitar el retroceso de la cadena 'S'.
2. Los Partidos KMP: Con la cadena 'S', el patrón 'p' y la función de prefijo 'Π' como entradas, encuentre la aparición de 'p' en 'S' y devuelva el número de desplazamientos de 'p' después de los cuales se encuentran las apariciones.
La función de prefijo (Π)
El siguiente pseudocódigo calcula la función de prefijo, Π:
<strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
Análisis de tiempo de ejecución:
En el pseudocódigo anterior para calcular la función de prefijo, el bucle for del paso 4 al 10 se ejecuta 'm' veces. Los pasos 1 a 3 toman un tiempo constante. Por tanto, el tiempo de ejecución de la función de prefijo de cálculo es O (m).
Ejemplo: Calcule Π para el patrón 'p' siguiente:
¿Cuál es la diferencia entre un megabyte y un gigabyte?
Solución:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
Después de iterar 6 veces, se completa el cálculo de la función de prefijo:
El KMP coincide:
El KMP Matcher con el patrón 'p', la cadena 'S' y la función de prefijo 'Π' como entrada, encuentra una coincidencia de p en S. El siguiente pseudocódigo calcula el componente de coincidencia del algoritmo KMP:
<strong>KMP-MATCHER (T, P)</strong> 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [q] // look for the next match
Análisis de tiempo de ejecución:
El bucle for que comienza en el paso 5 se ejecuta 'n' veces, es decir, tan largo como la longitud de la cadena 'S'. Dado que los pasos 1 a 4 toman tiempos constantes, el tiempo de ejecución está dominado por este para el ciclo. Por tanto, el tiempo de ejecución de la función coincidente es O (n).
Ejemplo: Dada una cadena 'T' y el patrón 'P' de la siguiente manera:
Ejecutemos el algoritmo KMP para encontrar si 'P' ocurre en 'T'.
Para 'p' la función de prefijo, ? fue calculado previamente y es el siguiente:
Solución:
Initially: n = size of T = 15 m = size of P = 7
Se ha descubierto que el patrón 'P' presenta complejidad en una cadena 'T'. El número total de turnos que tuvieron lugar para encontrar la coincidencia es i-m = 13 - 7 = 6 turnos.