[Algorithm] 라빈 카프 알고리즘

 

35강에 대한 리뷰

 

 

일반적인 경우 빠르게 작동하며 간단한 구조를 가진 문자열 매칭 알고리즘이다.

 

해시 기법을 이용하여 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다.

 

 

동일한 해시값이 발생하는 이른바 충돌이 발생할 수도 있는데 발생률이 낮아 무시하고 지나간다.

 

 

보통 공식은

 

긴 글 해시값 = 2 * (긴 글 해시값 - 가장 앞 문자의 값) + 새롭게 들어온 문자의 값

 

 

def find_string(parent, pattern):
    parent_len = len(parent)
    pattern_len = len(pattern)
    parent_hash = 0
    pattern_hash = 0
    power = 1
    for i in range(parent_len - pattern_len + 1):
        if i == 0:
            for j in range(pattern_len):
                parent_hash += ord(parent[pattern_len - 1 - j]) * power
                pattern_hash += ord(pattern[pattern_len - 1 - j]) * power
                if j < pattern_len - 1:
                    power *= 2
        else:
            parent_hash = 2 * (parent_hash - ord(parent[i - 1]) * power) + ord(parent[pattern_len - 1 + i])
            
        if parent_hash == pattern_hash:
            found = True
            for j in range(pattern_len):
                if parent[i + j] != pattern[j]:
                    found = False
                    break
            if found:
                print(f'{i + 1}번째에서 발견했습니다')
                
if __name__ == "__main__":
    parent = "ababacabacaabacaaba"
    pattern = "abacaaba"
    find_string(parent, pattern)

 

 

 

안정적인 프로그램 작성을 위해 나머지 연산(MOD)이 권장된다.

 

def find_string(parent, pattern):
    parent_len = len(parent)
    pattern_len = len(pattern)
    parent_hash = 0
    pattern_hash = 0
    power = 1
    for i in range(parent_len - pattern_len):
        if i == 0:
            for j in range(pattern_len):
                parent_hash += ord(parent[pattern_len - 1 - j]) * power
                pattern_hash += ord(pattern[pattern_len - 1 - j]) * power
                if j < pattern_len - 1:
                    # power *= 2
                    power *= 403
        else:
            # parent_hash = 2 * (parent_hash - ord(parent[i - 1]) * power) + ord(parent[pattern_len - 1 + i])
            parent_hash = 403 * (parent_hash - ord(parent[i - 1]) * power) + ord(parent[pattern_len - 1 + i])
        
        print(f'해시 값 비교 parent_hash: {parent_hash}, pattern_hash: {pattern_hash}')
            
        # if parent_hash == pattern_hash:
        #     found = True
        #     for j in range(pattern_len):
        #         if parent[i + j] != pattern[j]:
        #             found = False
        #             break
        #     if found:
        #         print(f'{i + 1}번째에서 발견했습니다')
                
if __name__ == "__main__":
    parent = "ababacabacaabacaaba"
    pattern = "abacaaba"
    find_string(parent, pattern)