[자료구조] 라빈 카프 문자열 매칭

라빈 카프 문자열 매칭(Rabin–Karp algorithm)

• ASCII 코드 기반의 해시 함수를 이용하여 특정한 문자열에 대한 해시 값을 구함
• 연속적인 문자열이 이어지는 상황이므로 해시 함수의 동작에 있어서 연산속도가 O(1)
• 라빈카프 문자열 매칭 알고리즘에서 해시함수는 각 문자의 ASCII 코드 값에 2의 제곱 수를 차례대로 곱하여 더한 값을 구함.
• 일반적으로 서로 다른 문자열의 경우 해시값이 다르게 나옴. 그러나 해시기반이기 때문에 충돌 처리 필요

다음 해시 값 = 2 * (현재 해시값 - 가장 앞에 있는 문자의 수치) + 새 문자의 수치

 

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수