라빈-카프 시각화
롤링 해시를 활용한 문자열 패턴 매칭 알고리즘을 단계별로 학습하세요
문자열★★☆
속도
1 / 1매칭 수: 0비교 횟수: 0거짓 양성: 0해시값: 0 vs 0
프리셋
각 단계를 클릭하면 해당 시점으로 이동합니다.
검색 버튼을 눌러 시작하세요.
라빈-카프란?
롤링 해시로 텍스트의 부분 문자열과 패턴의 해시값을 O(1)에 비교하여 패턴 매칭을 수행합니다. 다중 패턴 검색에 특히 강력합니다.
사용 방법
- 1텍스트와 패턴을 입력하고 검색하세요
- 2각 위치에서의 해시값 계산 과정을 관찰하세요
- 3해시 충돌(거짓 양성)이 발생하면 실제 비교가 이루어집니다
- 4베이스와 모듈러를 바꿔 충돌 빈도 변화를 확인하세요
동작 원리
- 1패턴의 해시값을 계산합니다
- 2텍스트의 윈도우를 한 칸씩 이동하며 롤링 해시로 O(1)에 해시값 갱신
- 3해시가 일치하면 실제 문자 비교로 확인 (스퍼리어스 히트 방지)
- 4평균 O(n+m), 최악 O(nm)이나 좋은 해시 함수로 거의 선형
실무 활용
- •표절 검사 — 여러 문서에서 동시에 패턴을 검색
- •바이러스 스캐너의 시그니처 다중 패턴 매칭
- •텍스트 에디터의 찾기/바꾸기 기능
- •네트워크 침입 탐지 시스템(IDS)의 패킷 패턴 매칭
비슷한 알고리즘
- •KMP — 단일 패턴에 최악 O(n+m) 보장, 라빈-카프는 다중 패턴에 강점
- •Aho-Corasick — 다중 패턴 동시 검색의 표준, 트라이 기반
- •Boyer-Moore — 실무에서 가장 빠른 단일 패턴 매칭, 뒤에서부터 비교
학습 팁
- •롤링 해시의 수학적 원리(다항식 해시)를 먼저 이해하세요
- •의도적으로 충돌이 발생하는 예시를 만들어보세요
- •KMP와 같은 텍스트·패턴에서 비교 횟수를 비교해보세요
자주 묻는 질문
Q. KMP보다 좋은가?
A. 다중 패턴 검색에서는 라빈-카프가 유리합니다. 단일 패턴에서는 KMP가 최악 보장이 있어 안정적입니다.
Q. 해시 충돌이 많으면?
A. 더 큰 모듈러나 이중 해시를 사용하여 충돌을 줄일 수 있습니다.