KMP 패턴 매칭 시각화
실패 함수를 활용한 O(n+m) 문자열 패턴 매칭 알고리즘
문자열★★☆
속도
1 / 1매칭 수: -현재 단계: 실패 함수 구축
프리셋
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
KMP 알고리즘이란?
KMP(Knuth-Morris-Pratt)는 텍스트에서 패턴을 O(n+m) 시간에 찾는 문자열 매칭 알고리즘입니다. 나이브 방법(O(n*m))과 달리, 불일치 발생 시 패턴의 '실패 함수'를 활용하여 불필요한 비교를 건너뜁니다.
사용 방법
- 1프리셋을 선택하거나 직접 텍스트와 패턴을 입력합니다
- 2실행 버튼을 눌러 1단계: 실패 함수 구축, 2단계: 검색을 시작합니다
- 3실패 함수 테이블(하단)이 채워지는 과정을 관찰합니다
- 4검색 단계에서 패턴이 텍스트 위를 슬라이드하는 것을 확인합니다
- 5매칭 위치가 초록색으로 하이라이트됩니다
동작 원리
- 11단계(실패 함수): 패턴 자체의 접두사-접미사 일치 길이를 미리 계산합니다. failure[i]는 pattern[0..i]에서 가장 긴 proper prefix == suffix의 길이입니다
- 22단계(검색): 텍스트와 패턴을 한 글자씩 비교합니다. 일치하면 둘 다 전진합니다
- 3불일치 시: pi를 failure[pi-1]로 설정하여 패턴을 효율적으로 이동시킵니다. 이미 일치한 접두사를 재활용합니다
- 4전체 패턴이 일치하면(pi == m) 매칭을 기록하고 failure를 사용해 다음 검색을 이어갑니다
실무 활용
- •텍스트 에디터의 찾기/바꾸기 기능
- •네트워크 침입 탐지 시스템(IDS)의 패턴 매칭
- •DNA 서열에서 특정 유전자 패턴 검색
- •컴파일러의 어휘 분석(lexical analysis)
학습 팁
- •실패 함수가 핵심입니다 — 이것이 왜 '건너뛰기'를 가능하게 하는지 이해하세요
- •'ABABC' 패턴의 실패 함수 [0,0,1,2,0]을 직접 손으로 계산해보세요
- •불일치 시 pi = failure[pi-1]이 왜 올바른지 생각해보세요
자주 묻는 질문
Q. KMP vs 라빈-카프 vs 보이어-무어의 차이는?
A. KMP: O(n+m) 보장, 실패 함수 사용. 라빈-카프: 해시 기반, 평균 O(n+m), 최악 O(nm). 보이어-무어: 뒤에서부터 비교, 실무에서 가장 빠른 경우가 많음. KMP는 최악 보장이 필요할 때 선택합니다.
Q. 실패 함수를 왜 'failure'라고 부르나요?
A. 불일치(failure) 시 어디로 돌아갈지 알려주기 때문입니다. 'partial match table' 또는 'prefix function'이라고도 합니다.