라빈-카프 알고리즘

1. 라빈-카프 알고리즘

라빈-카프 알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘

 

해시 값이 다르다면 두 문자열이 다르다는 것을 보장한다. 하지만 문자열이 달라도 해시 값이 같을 수 있다.

👉 우리는 이것을 Spurious Hit이라 한다.

Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요하다. 이 특징을 이용하여 라빈-카프 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시값과 일치하는지 비교하는 작업을 한다.

 

따라서 라빈-카프 알고리즘은 다음 문자열에 대한 해시 값을 계산해야 한다.

• 길이가 m인 패턴 자체
• 길이가 m인 텍스트의 모든 부분 문자열

 

2. 해시 함수

사용 예시

🟩 rolling hash

각 위치에서 해시 함수를 처음부터 다시 계산하는 것은 너무 느리다. 그렇기 때문에 rolling hash를 사용한다. rolling hash는 window 사이즈만큼 이동하면서 입력을 받아 해시값을 구한다.

👉 rolling hash를 통해 사용했던 결과를 재사용해서 해시 값을 빠르게 계산할 수 있다.

 

3. 시간복잡도

pattern의 길이를 M, text의 길이를 N이라 가정한다.

전처리 단계의 시간 복잡도는 O(M)이고, 문자열 검색 단계의 시간 복잡도는 O(N)이기 때문에 시간 복잡도는 O(M+N)이다. (해시값을 구할 때, 처음 한 번 구해놓으면, 다음 해시값을 구할 때는 가장 처음값을 해시값에서 빼주고, 새로 추가된 부분을 해시값에 더해주기만 하면 되기 때문)

최악의 경우엔, 해시 함수가 좋지 않아서 각각 다른 문자열이 공통된 해시값을 가질 경우 O(MN)의 시간복잡도를 갖는다.

---

참고자료

https://velog.io/@joon6093/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%9D%BC%EB%B9%88-%EC%B9%B4%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Rabin-Karp