목록라빈카프알고리즘 (1)

Binary Journey

[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: f..
Algorithm/알고리즘 스터디(2021.07) 2021. 11. 29. 21:24
이전 Prev 1 Next 다음