Rolling Hash

rsync라는 유틸리티를 알게되서 알아본 알고리즘.http://en.wikipedia.org/wiki/Rolling_hashhttp://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf예시를 이용한 정리. 다음 주어진 문자열 String 2를 String 1에서 검색 또는 비교하는 상황이라 하자.String 1: "abcdeabcdefaaa", String 2: "bcd"Naive한 방식은 문자열을 3개의 문자열 단위로 문자 하나씩 비교하는 방식이다. Rolling Hash 알고리즘을 사용해서 이 상황을 풀어보자. 과정 1-1. 먼저 String 2의 문자열 "bcd"의 Hash 값을 구해놓는다.Pattern = b*7^0 + c*7^1 d*7^2 = 98*1 +..

2015.01.22