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

Z-Algorithm

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 
 
 
 
 
  
 
 
Z Algorithm for String Matching
  
 
  Intermediate (3/5)
 
~1 hora   Z-array: longest substring starting at i that is also a prefix  O(n) preprocessing  Pattern matching sin LPS table  Z-box and L, R window  
Prereqs: String manipulation, KMP algorithm  
 
Quick Reference
Z-Algorithm
The Z-algorithm builds a Z-array over "pattern$text": z[i] is the length of the longest substring starting at i that matches a prefix of the string. Every position where z[i] equals the pattern length marks an occurrence.

Difficulty: Intermediate (3/5)
string
Complexity
Best Time
O(n)
Average Time
O(n)
Worst Time
O(n)
Space
O(n)
When to Use
Use the Z-algorithm when you want a compact linear-time pattern matcher that is easy to understand — the Z-array is also useful for other prefix-matching problems.
Pros
  • Truly linear in all cases
  • Simple invariant-based construction
  • Z-array is a reusable primitive
Cons
  • Requires the separator-joined string
  • Less well-known than KMP
  • O(n) extra space for the Z-array
History
The Z-algorithm was popularized by Dan Gusfield in his 1997 textbook "Algorithms on Strings, Trees and Sequences", though the core Z-array idea appeared in earlier linear-time pattern-matching work. It is a favorite for its elegant constant time-per-character argument.
 
 
Z Algorithm calcula la Z-array en tiempo lineal: Z[i] es la longitud del substring más largo que comienza en i y es también un prefix del string completo.


Es una alternativa a KMP para pattern matching y suffix array construction, con la misma complejidad O(n+m) pero conceptualmente más simple: mantén una ventana [L,R] del substring que coincide con el prefix.


Cómo Funciona


    

  1. Inicializa Z[0] = n (el string completo coincide consigo mismo).
    2. 

  2. Mantén ventana [L,R] donde S[L..R] coincide con S[0..R-L].
    3. 

  3. Para cada i de 1 a n-1:

      

    • Si i > R: calcula Z[i] por brute force desde i.
      • 

    • Si i <= R: usa conocimiento previo Z[i-L].

        

      • Si Z[i-L] < R-i+1: Z[i] = Z[i-L] (dentro de la ventana).
        • 

      • Si no: recalcula desde R+1 y extiende R.
        • 

      

      • 

    

    4. 

  4. Matching: concatena patrón + '$' + texto; busca Z[i] == m.
    5. 



Idea Clave


La ventana [L,R] codifica el substring más largo que coincide con el prefix y termina en R. Cuando estás dentro de la ventana (i <= R), ya sabes que S[i..R] coincide con S[i-L..R-L], por lo que Z[i] está al menos garantizado hasta R-i+1.


Si Z[i-L] es menor que R-i+1, el match está completamente dentro de la ventana y lo copias. Si no, necesitas extender R manualmente desde R+1.


Ejemplo Trabajado


String: ABABAB, n = 6.


Construcción de Z-array:


i=0: Z[0]=6 (por definición), L=0, R=5

i=1: i > R? No (1 <= 5). Z[1]=Z[0]=6, pero Z[0] >= R-i+1=5 → extiende desde R+1=6, fin. Z[1]=0.

i=2: i > R? Sí. Calcula brute force: S[2..]='ABAB' vs S[0..]='ABABAB' → 4 coinciden. Z[2]=4. L=2, R=5.

i=3: i <= R=5. Z[3]=Z[3-2]=Z[1]=0 < R-i+1=3 → Z[3]=0.

i=4: i <= R=5. Z[4]=Z[4-2]=Z[2]=4 >= R-i+1=2 → extiende desde 6, fin. Z[4]=2. L=4, R=5.

i=5: i <= R=5. Z[5]=Z[5-4]=Z[1]=0 < R-i+1=1 → Z[5]=0.


Z-array: [6, 0, 4, 0, 2, 0].


Pattern matching: ABC$ABABAB → busca Z[i]=3 (longitud de ABC).


Casos Extremos y Trampas


    

  • Todos caracteres iguales — AAAAAA: Z = [6,5,4,3,2,1], la ventana se expande cada vez.
    • 

  • Sin repeticiones — ABCDEF: Z = [6,0,0,0,0,0], sin Z-box útil.
    • 

  • Z[0] — por definición es n, pero para matching ignoramos índice 0.
    • 

  • Empty string — indefinido; retorna array vacío.
    • 



Comparación con KMP
































AspectoZ AlgorithmKMP
PreprocessingZ-array del texto completoLPS table del patrón
MatchingBusca Z[i] == mComparación carácter por carácter
ComplejidadO(n+m)O(n+m)
ConceptoVentana prefix-suffixPrefix function


Aplicaciones


    

  • Pattern matching — alternativa a KMP
    • 

  • Suffix array construction — base para algoritmos más avanzados
    • 

  • String periodicity — encontrar el periodo mínimo de un string
    • 

  • Enseñanza — introduce Z-box y ventanas deslizantes
    • 



Trayectoria de Práctica


    

  1. Implementa Z-array; traza ABABAB y AAAAAA.
    2. 

  2. Implementa pattern matching con patrón$texto.
    3. 

  3. Compara con KMP: ¿cuál es más fácil de implementar?
    4. 

  4. Investiga Z-algorithm para suffix arrays: ¿cómo ordena sufijos?
    5. 

  5. ¿Por qué Z[0]=n no se usa para matching?
    6.