라빈-카프1 라빈-카프 알고리즘 구현 꿀팁 라빈-카프의 전체적인 동작 원리를 설명하는 글은 아니다. 문자열 s = a0a1a2...를 해싱으로 f(s)로 보내버릴 때, 다항식을 f = a0 + a1 * c + a2 * c^2 + ... 이렇게 인덱스를 맞춰서 잡기보다는 거꾸로 f = an + a_(n-1) * c + ... 이렇게 잡는 게 더 구현이 쉽다. hashval = (hashval * c + s[i]) % M을 재귀적으로 반복해서 구현할 수 있기 때문. c의 모든 거듭제곱을 전처리하지 않아도 된다. C = c ^ k만 전처리해서 어디다가 저장해 두고 있어도 된다. 첫 번째 해시값을 구했으면 한 칸씩 옮기면서 다음 해시값을 hashval = (hashval * c + s[i] - C * s[i - k]) % M으로 O(1)에 구할 수 있다.. 2023. 2. 7. 이전 1 다음
