문자열 알고리즘Advanced

보이어-무어 문자열 매칭

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

#string#pattern-matching#heuristic#text-search

Complexity Analysis

Time (Average)

O(n)

Expected case performance

Space

O(m + σ)

Memory requirements

Time (Best)

O(n/m)

Best case performance

Time (Worst)

O(n × m)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 32•Section 32.5

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

KMP 문자열 매칭

Advanced

문자열에서 패턴을 효율적으로 찾는 Knuth-Morris-Pratt 알고리즘입니다. 실패 함수(LPS 배열)를 사용하여 불필요한 비교를 건너뛰어 O(n+m) 시간 복잡도를 달성합니다. 텍스트 검색, DNA 서열 분석, 표절 탐지에 필수적입니다.

O(n + m)

O(m)

stringpattern-matching

Start Learning

Back to 문자열 알고리즘