String-AlgorithmenAdvanced

KMP-String-Matching

Knuth-Morris-Pratt-Algorithmus fur effizienten Musterabgleich in Strings. Verwendet eine Fehlerfunktion (LPS-Array), um unnotige Vergleiche zu uberspringen und O(n+m) Zeitkomplexitat zu erreichen. Wesentlich fur Textsuche, DNA-Sequenzanalyse und Plagiaterkennung.

#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:

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 String-Algorithmen

Boyer-Moore-String-Matching

Advanced

Effizienter String-Suchalgorithmus, der Bad-Character- und Good-Suffix-Heuristiken verwendet. Vergleicht Muster von rechts nach links, was grosse Sprunge bei Nichtubereinstimmung ermoglicht. Erreicht in der Praxis sublineare Zeit und ist damit einer der schnellsten String-Matching-Algorithmen.

O(n)

O(m + σ)

stringpattern-matching

Start Learning

Back to String-Algorithmen