Algoritmo: KMP

NC > Computación > Algoritmo

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:
  1.  Knuth-Morris-Pratt algorithm - http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
  2. Rabin-Karp and Knuth-Morris-Pratt Algorithms - https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/
  3. Searching for Patterns | Set 2 (KMP Algorithm) - http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
  4. Algoritmo Knuth-Morris-Pratt - https://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt
0.06

No hay comentarios.:

Publicar un comentario