라빈-카프(Rabin-Karp) 알고리즘이란?
Rabin-Karp(라빈-카프) 알고리즘은 해싱(Hashing) 을 이용하여 긴 문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘입니다.
동작 방식
- 해시값 변환: 비교할 문자열과 찾고자 하는 패턴을 각각 해시 함수(Hash Function)를 통해 숫자 해시값으로 변환합니다.
- 해시값 비교: 두 해시값을 비교하여 일치하는지 확인합니다.
- 불일치: 해시값이 다르면, 두 문자열은 무조건 다른 것이므로 다음 문자열로 넘어갑니다.
- 일치: 해시값이 같으면, 두 문자열이 같을 가능성이 높으므로 실제 문자열을 직접 비교하여 완전히 일치하는지 최종 확인합니다. (해시 충돌 가능성 때문)
롤링 해시 (Rolling Hash)
라빈-카프 알고리즘은 효율적인 해시값 계산을 위해 롤링 해시 기법을 사용합니다.
- 슬라이딩 윈도우(Sliding Window) 처럼 한 칸씩 이동하며 해시값을 계산합니다.
- 새로운 문자가 윈도우에 들어오고 오래된 문자가 빠져나갈 때, 전체를 다시 계산하는 대신 변경되는 부분만 업데이트하여 중복 연산을 줄입니다.
이러한 방식으로 라빈-카프 알고리즘은 불필요한 문자열 비교를 최소화하여 검색 속도를 높입니다.