Rabin-Karp (1) 썸네일형 리스트형 88. Rabin-Karp 라빈-카프 알고리즘(Rabin-Karp Algorithm)은 해싱을 이용하여 문자열을 검색하는 알고리즘이다. 이 알고리즘은 주로 부분 문자열들이 동일한지의 여부를 빠르게 판별해야 하는 경우에 쓰이는데, 각각의 부분 문자열을 일일히 해싱하는 것은 시간이 너무 오래 걸리므로 더 빠른 방법이 요구된다. Rabin Fingerprint는 이러한 문제를 해결할 수 있는 해싱 방법으로, 다음과 같은 형태로 나타낼 수 있다. $$f(x, n) = \sum_{k=0}^n(s_k \cdot x^k) = s_0 + s_1x + s_2x^2 + \ldots + s_{n-1}x^{n-1} + s_nx^n$$ 일반적인 라빈-카프 알고리즘은 이 식을 약간 변형해서 다음과 같이 만든 다음 해시값을 계산한다. $$f(x, n) = .. 이전 1 다음
