Rabin-Karp’s algorithm(임시)

Rabin-Karp’s algorithm

Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length n, it performs in O(n+m) time with O(m) space, where m is the length of the pattern. It is often used in bioinformatics to search for DNA patterns.

라빈-카프 알고리즘은 해싱을 사용해 텍스트에서 패턴 문자열 세트 중 하나를 찾는 문자열 검색 알고리즘입니다. 평균 길이가 n인 문자열의 경우, O(m) 공간에서 O(n+m) 시간 내에 수행되며, 여기서 m은 패턴의 길이입니다. 생물 정보학에서 DNA 패턴을 검색하는 데 자주 사용됩니다.

 

 

라빈-카프 알고리즘(Rabin-Karp Algorithm)
라빈-카프 알고리즘은 문자열 검색 알고리즘의 한 종류로, 특정 문자열이 주어진 문자열 내에 존재하는지를 찾는 데 사용됩니다. 이 알고리즘의 핵심 아이디어는 해시 함수를 사용하는 것입니다. 해시 함수는 문자열을 숫자로 변환하고, 이 숫자를 비교함으로써 문자열이 동일한지를 판별합니다.

라빈-카프 알고리즘의 작동원리는 이렇습니다.
1. 찾고자 하는 패턴의 해시값을 계산합니다.
2. 그 다음, 주어진 문자열의 각 부분 문자열에 대한 해시값을 계산하고 이를 패턴의 해시값과 비교합니다.
3. 만약 해시값이 일치하면, 실제 문자열도 일치하는지 확인합니다.
4. 이렇게 해시값 비교와 문자열 비교를 통해 패턴이 문자열 내에 존재하는지를 찾아냅니다.

 

def rabin_karp(pattern, text, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d, m-1) % q
    p = 0
    t = 0
    result = []
    for i in range(m): # preprocessing
        p = (d*p + ord(pattern[i])) % q
        t = (d*t + ord(text[i])) % q
    for s in range(n-m+1): # note the +1
        if p == t: # check character by character
            match = True
            for i in range(m):
                if pattern[i] != text[s+i]:
                    match = False
                    break
            if match:
                result = result + [s]
        if s < n-m:
            t = (t - h*ord(text[s])) % q # remove letter s
            t = (t*d + ord(text[s+m])) % q # add letter s+m
            t = (t+q) % q # make sure that t >= 0
    return result

 

 

 

라빈-카프 알고리즘은 해시 함수를 통해 문자열 검색을 빠르게 수행할 수 있지만, 해시 충돌로 인한 오류 가능성이 있음을 유의해야 합니다. 이를 위해 실제 문자열 비교 단계가 필요한 것입니다.