Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

String Matching Visualizer

Knuth-Morris-Pratt

Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Comparisons 0
Matches Found 0
Status Ready
Text / Pattern
Comparing
Matched
Window / Aux highlight
Match found
Step Explanation

Select an algorithm and press Play to watch the pattern slide across the text.

—
Pseudocode 
 
 
 
 
  
 
 
Knuth-Morris-Pratt (KMP) String Matching
  
 
  Intermediate (3/5)
 
~1 hora   LPS array (longest proper prefix that is also suffix)  O(n + m) matching sin backtracking  Preprocessing O(m)  Pattern automaton implícito  
Prereqs: String manipulation, Prefix functions  
 
Quick Reference
Knuth-Morris-Pratt
KMP finds all occurrences of a pattern in a text in linear time by precomputing an LPS (longest proper prefix-suffix) table. When a mismatch occurs, the pattern shifts by a known safe amount instead of restarting the comparison.

Difficulty: Intermediate (3/5)
string
Complexity
Best Time
O(n)
Average Time
O(n)
Worst Time
O(n + m)
Space
O(m)
When to Use
Use KMP when you need all occurrences of a fixed pattern in a large text and want guaranteed linear worst-case behavior — no backtracking on the text pointer.
Pros
  • Linear worst case O(n + m)
  • The text pointer never moves backward
  • LPS table makes the "shift" logic explicit
Cons
  • More complex than naive scanning
  • Building LPS is a subtle step to get right
  • O(m) extra space for the table
History
The Knuth-Morris-Pratt algorithm was developed in 1974 and published in 1977 by Donald Knuth and Vaughan Pratt, working with James Morris. It was one of the first linear-time string-matching algorithms and introduced the prefix-function technique.
 
 
Knuth-Morris-Pratt (KMP) es un algoritmo de string matching que logra O(n + m) tiempo: n longitud del texto, m longitud del patrón. Lo logra preprocesando el patrón para crear una tabla LPS que indica cuánto puede “saltar” tras un mismatch.


A diferencia de la búsqueda naïve (que hace backtracking en el texto), KMP nunca retrocede en el texto: usa la LPS para reutilizar matches parciales.


Cómo Funciona


    

  1. 

    Preprocesa patrón para construir LPS:
    

      

    • lps[i] = longitud del longest proper prefix de pat[0..i] que también es suffix.
      • 

    • Dos punteros len (longitud prefix actual) y i (posición actual).
      • 

    • “Si pat[len] == pat[i]: len++, lps[i] = len.
      • 

    • Si no y len != 0: len = lps[len-1] (salta).
      • 

    • Si no y len == 0: lps[i] = 0.
      • 

    

    2. 

  2. 

    Matching con dos punteros i (texto) y j (patrón):
    

      

    • Si text[i] == pat[j]: i++, j++.
      • 

    • Si j == m: match encontrado.
      • 

    • Si mismatch y j != 0: j = lps[j-1] (salta en patrón).
      • 

    • Si mismatch y j == 0: i++.
      • 

    

    3. 



Idea Clave


La tabla LPS codifica la redundancia en el patrón. Cuando hay un mismatch en posición j, en vez de reiniciar el matching desde j=0, saltas a lps[j-1] porque ya sabes que los primeros lps[j-1] caracteres del patrón coinciden con el sufijo del texto actual.


Ejemplo: patrón ABABAC


    

  • ABAB tiene prefix AB y suffix AB → lps[3] = 2
    • 

  • Tras mismatch en ABABAX, sabes que AB ya coincide, no reinicias desde cero.
    • 



Ejemplo Trabajado


Patrón: ABABAC, texto: ABABABAC.


Tabla LPS:


i=0 (A): len=0, no match, lps[0]=0

i=1 (B): len=0, A≠B, lps[1]=0

i=2 (A): len=0, A==A, len=1, lps[2]=1

i=3 (B): len=1, B==B, len=2, lps[3]=2

i=4 (A): len=2, A==A, len=3, lps[4]=3

i=5 (C): len=3, C≠B, len=lps[2]=1, C≠A, len=lps[0]=0, lps[5]=0


LPS = [0, 0, 1, 2, 3, 0].


Matching:


    

  • i=0,j=0: A==A → i=1,j=1
    • 

  • i=1,j=1: B==B → i=2,j=2
    • 

  • i=2,j=2: A==A → i=3,j=3
    • 

  • i=3,j=3: B==B → i=4,j=4
    • 

  • i=4,j=4: A==A → i=5,j=5
    • 

  • i=5,j=5: B≠C, j=lps[4]=3
    • 

  • i=5,j=3: B==B → i=6,j=4
    • 

  • i=6,j=4: A==A → i=7,j=5
    • 

  • i=7,j=5: C==C → i=8,j=6 → match en i=2
    • 



Resultado: match encontrado en índice 2 del texto.


Casos Extremos y Trampas


    

  • Patrón repetitivo — AAAA tiene LPS [0,1,2,3]; tras mismatch salta poco.
    • 

  • Patrón sin self-overlap — ABCD tiene LPS [0,0,0,0]; salta a 0 tras mismatch.
    • 

  • Múltiples matches — KLS encuentra todos los matches; usa lps[j-1] para continuar.
    • 

  • Edge case vacío — patrón "" no tiene sentido; texto "" no tiene matches.
    • 



Comparación





































AlgoritmoTiempoEspacioBacktrack texto
NaiveO(nm)O(1)Sí
KMPO(n+m)O(m)No
Rabin-KarpO(n+m) avgO(1)No
Boyer-MooreO(n/m) bestO(m)No


Aplicaciones


    

  • Editores de texto — find/replace, syntax highlighting
    • 

  • Detección de plagio — búsqueda de patrones en documentos
    • 

  • Bioinformática — búsqueda de secuencias en ADN
    • 

  • Seguridad — detección de firmas en tráfico de red
    • 



Trayectoria de Práctica


    

  1. Implementa construcción de LPS; traza ABABAC y AAAA.
    2. 

  2. Implementa KMP matching; traza el ejemplo paso a paso.
    3. 

  3. Compara con naive: cuenta comparaciones en un texto de 1000 chars.
    4. 

  4. Investiga Z-algorithm: ¿por qué es equivalente a LPS?
    5. 

  5. Investiga Boyer-Moore: ¿cuándo es mejor que KMP?
    6. 



”