Algorithmes de chaînesAdvanced
Correspondance de chaînes KMP
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.
#string#pattern-matching#preprocessing#text-search
Complexity Analysis
Time (Average)
O(n + m)Expected case performance
Space
O(m)Memory requirements
Time (Best)
O(n)Best case performance
Time (Worst)
O(n + m)Worst case performance
📚 CLRS Reference
Introduction to Algorithms•Chapter 32•Section 32.4
Presets:
Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation