Para ser honesto, KMP es uno de los algoritmos más difíciles de aprender que he visto. Me llevó casi un día entero finalmente darme cuenta de cómo funciona. Para cualquiera que esté tratando de aprenderlo, aquí hay algunos consejos que ayudarán.
Digamos que tenemos un texto T y un patrón P que queremos buscar. Lo primero que hace KMP es que, para cada índice de P, calcula la siguiente función:
K [i] = prefijo propio más largo de P [i], que también es un sufijo de P [i]
- Si pudiera romper el algoritmo RSA, ¿lo mantendría en secreto?
- ¿Cuál es la diferencia entre los algoritmos Reheap up y Reheap down?
- ¿Cómo diseñaría un algoritmo para clasificar 100 millones de libros y encontrar duplicados funcionales?
- ¿Cuáles son las formas de ajustar algoritmos de aprendizaje automático?
- ¿Cuáles son algunos ejemplos de uso no trivial de la búsqueda binaria?
Este es el quid del algoritmo. La idea detrás de esto es que supongamos que primero los caracteres i de P coinciden con T, pero luego hay un desajuste en el carácter (i + 1). Ya sabemos la longitud del prefijo más largo de P que es el sufijo de P. Por lo tanto, ya sabemos que P [K [i]] coincide con T [j..i], y así podemos reanudar el procedimiento de comparación comparando P [K [i] + 1] con T [i + 1].
Ahora, la parte difícil es el cálculo de K. Se calcula utilizando un algoritmo de programación dinámico.
- Para i = 0, K [i] será 0 (= L), (ya que la longitud del prefijo apropiado es 0).
- Para i> 0, hay 2 casos:
- P [i] = P [L], en este caso, K [i] es simple ++ L;
- P [i]! = P [L], coincide recursivamente con el siguiente prefijo más pequeño. es decir, L = K [L]
Espero que esto ayude.
