Rabin-Karp 알고리즘

Rabin-Karp 알고리즘

해시 함수를 사용하여 패턴과 텍스트 부분 문자열의 해시 값을 비교하는 문자열 매칭 알고리즘으로, 다중 패턴 검색에 효율적이며 롤링 해시로 O(n+m) 평균 시간 달성

목적: 다중 패턴 검색, 표절 검사, 문자열 매칭

특징: 해시 기반, 롤링 해시, 다중 패턴 효율적, 충돌 처리 필요

롤링 해시(Rolling Hash): 슬라이딩 윈도우에서 해시를 O(1)에 갱신, hash(s[i+1..i+m]) = (hash(s[i..i+m-1]) - s[i]×base^(m-1))×base + s[i+m]

동작: ① 패턴 해시 계산 → ② 텍스트 첫 윈도우 해시 계산 → ③ 해시 일치 시 실제 문자열 비교(충돌 대비) → ④ 롤링 해시로 다음 윈도우 이동 → ⑤ 반복

해시 함수: 다항 해시 hash(s) = Σ s[i]×base^(m-1-i) mod prime, base=보통 256, prime=큰 소수

시간 복잡도: 평균 O(n+m), 최악 O(nm) - 모든 해시 충돌

공간 복잡도: O(1)

장점: 다중 패턴 효율(k개 패턴 O(n+km)), 단순 구현, 평균 빠름, 2D 패턴 가능

단점: 해시 충돌 가능, 최악 O(nm), 실제 문자열 비교 필요

적용사례: 표절 검사, 다중 패턴 검색, 이미지 패턴 매칭, 바이러스 스캐너, 중복 파일 찾기

비교: Rabin-Karp(해시/다중패턴) vs KMP(전처리/단일패턴) vs Aho-Corasick(트라이/다중패턴)

연관: 해시, 롤링 해시, 문자열 매칭, 다중 패턴