Algorithmes de chaînesAdvanced

Correspondance de chaînes Boyer-Moore

Algorithme de recherche de chaînes efficace utilisant les heuristiques de mauvais caractère et de bon suffixe. Compare le motif de droite à gauche, permettant de grands sauts en cas de non-correspondance. Atteint un temps sous-linéaire en pratique, ce qui en fait l'un des algorithmes de correspondance de chaînes les plus rapides.

#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 Algorithmes de chaînes

Correspondance de chaînes KMP

Advanced

Algorithme de Knuth-Morris-Pratt pour la correspondance efficace de motifs dans les chaînes. Utilise une fonction d'échec (tableau LPS) pour sauter les comparaisons inutiles, atteignant une complexité temporelle O(n+m). Essentiel pour la recherche de texte, l'analyse de séquences ADN et la détection de plagiat.

O(n + m)

O(m)

stringpattern-matching

Start Learning

Back to Algorithmes de chaînes