[Python] 문자열 검색 - 라빈-카프 알고리즘(Rabin-Karp Algorithm)

문자열 검색 알고리즘은 우리가 자주 쓰는 'cntl + F'에 대한 알고리즘이다.

현재 쓰이는 것은 크게 3가지가 있는 것 같다.

 

0. 브루트포스 - 한글자, 한글자 매칭해가며 찾는 방법 - $O(nm)$

1) 라빈-카프 알고리즘에서 해시값이 같을 때, 마지막 검증수단으로 쓰이기도 함.

1. KMP 알고리즘(Knuth–Morris–Pratt, KMP) - $O(n+m)$

2. 라빈-카프 알고리즘(Rabin_karp) - $O(n+m)$  혹은 $O(nm)$

3. 보이어-무어 알고리즘(Boyer-Moore) - 일반적 $O(n)$보다 적다고 함. 혹은 최악의 경우 $O(nm)$

 

[Python] 백준 - 1786 찾기

1. KMP 알고리즘(Knuth–Morris–Pratt, KMP)

 

2. 라빈-카프 알고리즘(Rabin_karp)

 

패턴 문자열(검색어)의 해시값, 텍스트 문자열(검색대상글)의 해시값을 비교해 같으면, 직접 문자비교를 한다.

롤링해시를 통해 중복계산을 줄여준다. 해시함수에 대한 것은 따로 파고들어야 할 듯 하다. 

잘 설명되어 있는 블로그가 많아, 그냥 개인적으로 까먹었을 때 떠올리고자 올림. 코드를 직접 작성해보면 이해가 어렵진 않다.

 

import sys
input = sys.stdin.readline

t = 'doolystardoolytool'
p = 'dooly'

def check(s, p, i, n, m): # Naive 알고리즘 문자열 직접 비교
    pdx = 0
    while pdx < m and s[i+pdx] == p[pdx]: # 받아온 i자리에서부터 패턴과 비교
        pdx += 1
    if pdx == m: # 끝까지 같으면 True
        return True
    return False # 아니면 False

def rabin_karp(t, p):
    n, m = len(t), len(p)
    res = []
    hp, ht = 0, 0
    d, h = 256, 1 # ascii표현가능숫자(d), 소수(q)
    q = 7
    for i in range(m-1): # 시계태엽 m-1번 감은 값
        h = (h * d) % q
    for i in range(m): # p(패턴문자열)과 t(텍스트문자열)에 대해 시계태엽감기
        hp = (d * hp + ord(p[i])) % q
        ht = (d * ht + ord(t[i])) % q
    for i in range(n-m+1):
        if hp == ht: # 해시값이 패턴값과 동일하면
            if check(t, p, i, n, m): # 문자열 비교 후 res에 넣어줌
                res.append(i)
        if i < n-m:
            ht = (d * (ht - ord(t[i]) * h) + ord(t[i+m])) % q # 롤링해시
            # 첫 원소값은 태엽이 m-1번 감겨있음.
            # 1에 대해 태엽을 m-1번 감은 h를 첫원소값에 곱해서 빼주고 i+len(p)자리 새로 반영
            if ht < 0: # 결과가 음수일시, q를 한번더 더해줌.(-ht % q == -ht+q % q) 
                ht += q
    return res

print(rabin_karp(t, p))