크누스-모리스-프랫 알고리즘
크누스-모리스-프랫 알고리즘은 텍스트에서 패턴이 등장하는 위치를 접두사 일치 정보를 이용하여 선형 시간에 찾는다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므...
| 분류 | 알고리즘 · 문자열 패턴 검색 |
|---|---|
| 핵심 문제 | 텍스트에서 패턴이 등장하는 위치를 접두사 일치 정보를 이용하여 선형 시간에 찾는다 |
| 방법 | 패턴의 각 접두사와 접미사가 일치하는 최대 길이를 prefix 함수 또는 실패 함수로 전처리한다 |
| 계산 비용 | 텍스트 길이 n·패턴 길이 m에서 O(n+m), 보조 O(m) |
| 적용 조건 | 패턴과 텍스트의 문자 단위 비교가 정의되어야 한다 |
| 관련 활용 | 정확한 부분 문자열 검색에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
크누스-모리스-프랫 알고리즘은 텍스트에서 패턴이 등장하는 위치를 접두사 일치 정보를 이용하여 선형 시간에 찾는다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 패턴의 각 접두사와 접미사가 일치하는 최대 길이를 prefix 함수 또는 실패 함수로 전처리한다. 불일치가 발생하면 이미 확인한 문자를 다시 비교하지 않고 그 길이만큼 패턴의 위치를 이동한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 텍스트 길이 n·패턴 길이 m에서 O(n+m), 보조 O(m) 적용 전제는 패턴과 텍스트의 문자 단위 비교가 정의되어야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 정확한 부분 문자열 검색에 사용한다. 보이어-무어 알고리즘은 비교 순서·건너뛰기 규칙이 다르며 라빈-카프 알고리즘은 해시를 이용한다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]