¿Cuál es el mejor recurso para aprender el algoritmo KMP?

Lo aprendí de “Introducción a los algoritmos” de cormen, etc. Pero eche un vistazo a este enlace: Página en indstate.edu, ¡tal vez lo ayude!

Hay una semana completa en KMP en el curso Algorithms on Strings en Coursera.

Vaya a través de esta página y lea con claridad e intente comprender las complejidades.
Buscando patrones | Conjunto 2 (Algoritmo KMP) – GeeksforGeeks

Además, cuando crea que tiene una idea general sobre el funcionamiento de este algoritmo, pruebe algunos problemas:

Búsqueda de patrones | Práctica | GeeksforGeeks

SPOJ.com – PERIODO del problema

SPOJ.com – Problema NHAY

SPOJ.com – Problema EPALIN

SPOJ.com – Problema FILRTEST

El algoritmo KMP requiere calcular la matriz de sufijos de prefijo más larga lps []. Aquí está la implementación con video y ejemplos: El cómputo de matriz de sufijo de prefijo más largo en el algoritmo de coincidencia de patrones KMP.

El algoritmo KMP usa un valor de lps [] para decidir la siguiente posición deslizante. lps [i] denota la longitud del sufijo apropiado más largo que también es un prefijo apropiado para una cadena formada por caracteres del índice 0 al índice ‘i’ (incluyendo ‘i’).

Aquí hay un video tutorial sobre el algoritmo KMP:

También se puede encontrar una explicación detallada en este enlace:

El algoritmo Knuth Morris Pratt para la coincidencia de patrones.

Espero que esto ayude.

“Algoritmos sobre cuerdas, árboles y secuencias: informática y biología computacional” de Dan Gusfield es bueno para explicar esto. También contiene una discusión exhaustiva sobre la complejidad del algoritmo.

Este video mío explica KMP en detalle. Si entiendes un poco de hindi, entonces mira esto.

Estas dos conferencias contienen una explicación profunda de KMP, aunque un poco larga, pero vale la pena.

• Wikipedia tiene una entrada bastante buena con un ejemplo trabajado: http://en.wikipedia.org/wiki/Knu …
• También puede ver una explicación de David Eppstein: http://www.ics.uci.edu/~eppstein …
• Otra buena explicación de FH Flensburg – http://www.inf.fh-flensburg.de/l …

Aprendí el algoritmo KMP del video de Tushar Roy disponible en youtube. Él explica muy bien. Hay detalles de implementación al final del video, pero le recomendaría que aprenda el algoritmo y lo implemente usted mismo. Adjuntaré los enlaces para los videos aquí:

Knuth – Morris – Pratt (KMP) Coincidencia de patrones (búsqueda de subcadenas) Parte 1

Knuth – Morris – Pratt (KMP) Coincidencia de patrones (búsqueda de subcadenas) Parte2

¡Feliz codificación!

Pasé mucho tiempo entendiendo estos algoritmos pero no conseguí mucho. Finalmente obtuve esto:

El algoritmo de Knuth-Morris-Pratt en mis propias palabras

Da una muy buena explicación de KMP !!!

Tengo una explicación simple, no para todo el algoritmo, sino para la función de falla en el algoritmo KMP aquí: algoritmo de coincidencia de patrones KMP: función de falla

Puede ser útil 🙂

http://www.cs.nthu.edu.tw/~wkhon …
Estas diapositivas proporcionan explicaciones claras y no detalladas sobre cómo funciona el algoritmo KMP. El pseudocódigo real se puede encontrar en Introducción a los algoritmos de Cormen.

Como no podía entender las explicaciones que encontré en Internet, seguí buscando artículos, que fue cuando me encontré con esto:

El algoritmo de Knuth-Morris-Pratt en mis propias palabras

Esto no solo se explica perfectamente, sino que no es detallado como todos los otros artículos que encontré.

Espero eso ayude.

Introducción a los algoritmos de Cormen. Tiene una buena explicación junto con los autómatas con los que funciona.

Esto explica muy bien la lógica.
El algoritmo de Knuth-Morris-Pratt en mis propias palabras

estas dos conferencias son suficientes para tener una idea básica sobre el algoritmo KMP
Knuth – Morris – Pratt (KMP) Coincidencia de patrones (búsqueda de subcadenas)
Knuth – Morris – Pratt (KMP) Coincidencia de patrones (búsqueda de subcadenas) Parte2

Esta es una explicación breve pero descriptiva del algoritmo junto con algunos pseudocódigo.

Enlace: Búsqueda a través del texto

Fue escrito por Satwant Rana, quien fue mi compañero de equipo en ICPC 2015 y 2016.

Encontré este tutorial de Topcoder realmente bueno. http://community.topcoder.com/tc …

Aprendí kmp hace solo dos o tres días y ahora entiendo cómo funciona, así que tuve ganas de responder esto.
En primer lugar, para comprender cómo rellenamos los valores en función
http://jakeboxer.com/blog/2009/1 …
Ahora para comprender cómo se realiza la correspondencia y se realiza el cambio
http://www.mathcs.emory.edu/~che …
Puede obtener el código para kmp algo de geeksforgeeks.
Siéntese con un papel y un bolígrafo e intente comprender la forma en que funciona el código trabajando.
Ahora intenta resolver spoj -NHAY (usa el vector aquí)
FINDSR: búsqueda de raíces de cadena: utiliza el concepto de sufijo prefijo longet.