Algoritmos de CadenasAdvanced

Coincidencia de Cadenas Boyer-Moore

Algoritmo eficiente de búsqueda de cadenas usando heurísticas de carácter malo y sufijo bueno. Compara el patrón de derecha a izquierda, permitiendo grandes saltos en caso de no coincidencia. Logra tiempo sublineal en la práctica, convirtiéndolo en uno de los algoritmos de coincidencia de cadenas más rápidos.

#string#pattern-matching#heuristic#text-search

Complexity Analysis

Time (Average)

O(n)

Expected case performance

Space

O(m + σ)

Memory requirements

Time (Best)

O(n/m)

Best case performance

Time (Worst)

O(n × m)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 32•Section 32.5

Text

Pattern

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Algoritmos de Cadenas

Coincidencia de Cadenas KMP

Advanced

Algoritmo de Knuth-Morris-Pratt para coincidencia eficiente de patrones en cadenas. Usa una función de falla (arreglo LPS) para saltar comparaciones innecesarias, logrando complejidad de tiempo O(n+m). Esencial para búsqueda de texto, análisis de secuencias de ADN y detección de plagio.

O(n + m)

O(m)

stringpattern-matching

Start Learning

Back to Algoritmos de Cadenas