KMP
El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena.[4]
Complejidad:
Esto lleva a su peor caso de complejidad de Θ (nm) (n: longitud del texto, m: longitud del patrón) - This leads to its worst case complexity of Θ(nm) (n: length of the text, m: length of the pattern). [1]
Links:
- Knuth-Morris-Pratt algorithm - http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
- Rabin-Karp and Knuth-Morris-Pratt Algorithms - https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/
- Searching for Patterns | Set 2 (KMP Algorithm) - http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
- Algoritmo Knuth-Morris-Pratt - https://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt
0.06
No hay comentarios.:
Publicar un comentario