에듀테크 프로젝트 대시보드
라빈-카프 문자열 검색 (Rabin–Karp)
긴 텍스트에서 짧은 패턴을 찾을 때, 단순 방법은 모든 시작 위치마다 패턴 길이만큼
글자를 하나하나 비교한다 → O(n·m).
라빈–카프는 패턴과 텍스트 창(window)을 각각 숫자 하나(해시값)로 바꿔 놓고,
해시값이 같을 때만 실제 글자를 비교한다.
핵심은 창을 오른쪽으로 한 칸 옮길 때 해시를 처음부터 다시 계산하지 않고,
나가는 글자를 빼고 들어오는 글자를 더하는 O(1) 연산 —
이것이 롤링 해시(rolling hash)다.
문자열을 base 진법 수처럼 본다. 각 글자를 코드값으로 바꾸고 자리값을 곱해 더한다.
아래는 길이 m 창의 해시를 한 칸 옮기는 갱신식 (mod q 는 생략).
base = 256 (바이트 값), q = 소수(모듈러). q 를 작게 잡으면 서로 다른 문자열이 우연히 같은 해시가 되는 충돌(헛맞음, spurious hit)이 자주 일어나 눈으로 관찰할 수 있다. 실전에서는 q 를 큰 소수로 잡는다.
파랑 = 현재 창 · 초록(위로) = 새로 들어오는 글자 · 빨강(아래로) = 빠져나가는 글자 · 주황 = 해시 일치로 글자 검증 중 · 보라 = 해시는 같았지만 글자가 다른 헛맞음.
해시가 잘 분산되면 창마다 숫자 하나만 비교. 실제 글자 비교는 진짜 매칭 지점에서만 일어난다.
해시가 계속 충돌하면 매번 글자 검증까지 내려간다. 나쁜 q 나 악의적 입력에서 발생.
찾을 패턴이 여러 개일 때, 패턴 해시들을 집합에 넣고 창 해시 하나로 한 번에 조회 → 표절 검사, 스팸 시그니처 매칭에 유리.
2차원 패턴 매칭, rsync·git의 파일 청크 분할(콘텐츠 기반 분할),
문서 유사도(shingle) 등 롤링 해시 자체가 널리 쓰인다.
def rabin_karp(text, pat, base=256, q=1_000_000_007): n, m = len(text), len(pat) if m > n: return high = pow(base, m - 1, q) # 맨 앞 자리값 base^(m-1) mod q hp = ht = 0 for i in range(m): # 패턴 해시 + 첫 창 해시 (O(m)) hp = (hp * base + ord(pat[i])) % q ht = (ht * base + ord(text[i])) % q for i in range(n - m + 1): if hp == ht: # 해시 일치 → 실제 글자 확인 if text[i:i + m] == pat: yield i # 진짜 매칭 # else: 헛맞음(해시 충돌) if i < n - m: # 창을 한 칸 굴린다 (O(1)) ht = (ht - ord(text[i]) * high) % q # 나가는 글자 제거 ht = (ht * base + ord(text[i + m])) % q # 들어오는 글자 추가 ht %= q # 음수 보정
ht - ord(text[i]) * high 가 음수가 될 수 있으므로 파이썬이 아닌 언어에서는
((ht % q) + q) % q 로 반드시 양수로 만든다.