Rabin-Karp Substring Search Algorithm

Rabin Karp 알고리즘은 문자열 매칭 알고리즘이며 문자열 매칭을 O(n)의 시간안에 수행하게 해주는 알고리즘이다.

 

문자열 매칭은 다음과 같은 사례가 있다.

우리가 찾고자 하는 문자열을 target이라고 하고 대상이 되는 문자열을 S라고 했을때

아래 그림처럼 문자열을 하나씩 옮겨가면서 BruteForce 방식으로 찾게되면 len(target)*len(S)의 time complexity가 소요되게 된다. 즉 O(n**2)이라고 봐도 무방한것이다.

출처 : https://brilliant.org/wiki/rabin-karp-algorithm/

Rabin karp 알고리즘은 이러한 brute force방식의 문제점을 해결하여 O(n) time complexity로 문자열을 찾는 알고리즘이다.

핵심아이디어는 다음과 같다.

* brute force방식으로 문자열의 자리를 하나씩 옮겨가며 비교하지 말고 해시값을 구하여 일치하는지 비교하기(해시값은 유일함으로)

* 만약 해시값이 일치하지 않다면 한자리를 옮기고 옮긴 한자리에 대해서만 hash value를 구해서 비교를 해주면 된다. 즉 이전처럼 새롭게 한자리를 옮긴 문자열을 비교할때 len(target)*len(S)의 시간이 소요되는것이 아닌 새롭게 옮긴 값에 대해서만 hash value를 변경해주면 됨으로 O(1)의 시간이 소요되게 된다. (자세한 사항은 사실 영상을 봐야된다..)

 

출처 : https://www.sparknotes.com/cs/searching/hashtables/section4/

 

hash value를 구하는 방법으로는 여러가지 방법이 활용될 수 있다.

아래 코드는 hash value를 문자열을 ascii의 숫자로 변경을 해주어 더해주고 임의로 정한 수의 나머지를 구해주는 원리로 구하여 문자열을 비교해준다.

 

# pat  -> pattern
# txt  -> text
# q    -> A prime number
d = 12 # hash value를 구하기 위한 임의의값
q = 102 # hash value를 구하기 위한 임의의값

def search(pat, txt):
    M = len(pat)
    N = len(txt)

    i = 0
    j = 0
    p = 0  # hash value for pattern
    t = 0  # hash value for txt
    h = 1

    # The value of h would be "pow(d, M-1)%q"
    for i in range(M - 1):
        h = (h * d) % q

    # Calculate the hash value of pattern and first window of text
    for i in range(M):
        p = (d * p + ord(pat[i])) % q
        t = (d * t + ord(txt[i])) % q

    # Slide the pattern over text one by one
    for i in range(N - M + 1):
        # Check the hash values of current window of text and
        # pattern if the hash values match then only check
        # for characters one by one
        if p == t:
            # Check for characters one by one
            for j in range(M):
                if txt[i + j] != pat[j]:
                    break
                else:
                    j += 1

            # if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            if j == M:
                print("Pattern found at index " + str(i))

        # Calculate hash value for next window of text: Remove
        # leading digit, add trailing digit
        if i < N - M:
            t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q

            # We might get negative values of t, converting it to
            # positive
            if t < 0:
                t = t + q


# Driver Code
if __name__ == '__main__':
    txt = "GEEKS FOR GEEKS"
    pat = "GEEK"

    # Function Call
    search(pat, txt)
    
    
#### output ####
Pattern found at index 0
Pattern found at index 10

 

 

출처 : https://www.youtube.com/watch?v=qgsAZe5XhP0&t=402s

https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/

Rabin-Karp Algorithm for Pattern Searching - GeeksforGeeks