문자열 알고리즘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 문자열 알고리즘

보이어-무어 문자열 매칭

Advanced

나쁜 문자와 좋은 접미사 휴리스틱을 사용하는 효율적인 문자열 검색 알고리즘입니다. 패턴을 오른쪽에서 왼쪽으로 비교하여 불일치 시 큰 점프를 허용합니다. 실제로 준선형 시간을 달성하여 가장 빠른 문자열 매칭 알고리즘 중 하나입니다.

O(n)

O(m + σ)

stringpattern-matching

Start Learning

Back to 문자열 알고리즘