文字列アルゴリズムAdvanced

KMP文字列マッチング

文字列内の効率的なパターンマッチングのためのKnuth-Morris-Prattアルゴリズムです。失敗関数（LPS配列）を使用して不要な比較をスキップし、O(n+m)の時間計算量を達成します。テキスト検索、DNA配列分析、盗作検出に不可欠です。

#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 文字列アルゴリズム

Boyer-Moore文字列マッチング

Advanced

悪い文字ヒューリスティックと良い接尾辞ヒューリスティックを使用した効率的な文字列検索アルゴリズムです。パターンを右から左に比較し、不一致時に大きなジャンプを可能にします。実際にはサブリニア時間を達成し、最速の文字列マッチングアルゴリズムの1つです。

O(n)

O(m + σ)

stringpattern-matching

Start Learning

Back to 文字列アルゴリズム