rolling hash function (1) 썸네일형 리스트형 문자열 매칭 알고리즘[1](라빈 카프)[String Searching Algorithm, Rabin-Karp] 문자열 S에서 패턴 P를 찾는다고 해보자. 기본적으로 생각나는 방법은 S의 시작 위치에서 P가 나오는지 검사하는 것이다. s[0]부터 P와 같은지?, s[1]부터 p와 같은지?, s[2]부터 p와 같은지?, ... 이 경우에 시간복잡도는 O(|S|x|P|)이다. 일번적으로 비교할 경우 너무 비효율적이어서 사용하기 어렵다. 문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 1. 라빈 카프 알고리즘 정의 해쉬(Hash)함수를 사용해서 문자열에서 특정 문자열과 일치하는지 찾아주는 알고리즘이다. 2. 라빈 카프 알고리즘의 개념 해쉬함수 : 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어주는 함수(어떤 문자열을 정수로 표현하는 함수) 라빈 카프 알고리즘은 문자열을 정수로 바.. 이전 1 다음
