[알고리즘] Rabin Karp 라빈카프 (소스 코드)

1. Rabin Karp란?* Rabin Karp : text(문자열)에서 pattern(문자열)을 찾는 알고리즘* 해시가 기반이다.* 주로 사용되는 해시함수는 Rabin fingerprint이다.2. 알고리즘 작동 과정tLen : 문자열 text의 길이pLen : 문자열 pattern의 길이i) 문자열 text에서 길이가 pLen인 부분문자열들을 해쉬값을 구하고 해시에 저장한다.위에서 언급했다 싶이 "Rabin fingerprint"라는 해시 함수를 이용합니다.H(i)값을 매번 새로 구하면, 매번 O(pLen)의 시간이 걸리게 되는데사실 매번 구할 필요가 없습니다.H[i] = text[i] * 2^(n-1)+ text[i + 1] * 2^(n-2) + ...... + text[i + n - 1]H[i + 1] = text[i + 1] ..........

원문링크 : [알고리즘] Rabin Karp 라빈카프 (소스 코드)