라빈-카프 알고리즘
라빈-카프 알고리즘은 부분 문자열의 해시를 비교하여 후보 위치를 효율적으로 찾는다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별...
| 분류 | 알고리즘 · 문자열 패턴 검색 |
|---|---|
| 핵심 문제 | 부분 문자열의 해시를 비교하여 후보 위치를 효율적으로 찾는다 |
| 방법 | 패턴의 해시와 텍스트의 길이 m 윈도우 해시를 비교하며 롤링 해시로 한 글자 이동 시 값을 갱신한다 |
| 계산 비용 | 기대 O(n+m), 충돌이 빈번하면 최악 O(nm) |
| 적용 조건 | 같은 문자열이 같은 해시를 얻어야 하고 해시 충돌의 처리 정책을 정해야 한다 |
| 관련 활용 | 다중 패턴과 중복 부분 문자열 검출 등에 응용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
라빈-카프 알고리즘은 부분 문자열의 해시를 비교하여 후보 위치를 효율적으로 찾는다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 패턴의 해시와 텍스트의 길이 m 윈도우 해시를 비교하며 롤링 해시로 한 글자 이동 시 값을 갱신한다. 해시가 같을 때 실제 문자열을 비교하면 충돌로 인한 오탐을 없앨 수 있다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 기대 O(n+m), 충돌이 빈번하면 최악 O(nm) 적용 전제는 같은 문자열이 같은 해시를 얻어야 하고 해시 충돌의 처리 정책을 정해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 다중 패턴과 중복 부분 문자열 검출 등에 응용한다. 충돌 확률은 해시 함수·모듈러 선택과 입력 분포에 달려 있다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]