Dynamische ProgrammierungIntermediate
Langste gemeinsame Teilfolge (LCS)
Findet die langste Teilfolge, die in zwei Sequenzen in derselben Reihenfolge vorhanden ist. Verwendet dynamische Programmierung zum Aufbau einer Losungstabelle. Anwendungen umfassen DNA-Sequenzabgleich, Dateiunterschied-Tools (diff) und Plagiaterkennung.
#dynamic-programming#strings#sequences#optimization
Complexity Analysis
Time (Average)
O(m × n)Expected case performance
Space
O(m × n)Memory requirements
Time (Best)
O(m × n)Best case performance
Time (Worst)
O(m × n)Worst case performance
📚 CLRS Reference
Introduction to Algorithms•Chapter 15•Section 15.4
LCS finds the longest subsequence common to both strings
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