목록문자열 검색 (1)

넘치게 채우기

문자열 패턴 검색: 2 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm)

설명Naive 패턴 검색에서는, 우리는 모든 pattern의 길이와 같은 부분문자열들을 원본 문자열에서 추출해서 각각 한 글자씩 비교했다. Rabin-Karp 알고리즘에서도, 모든 부분문자열을 검사하지만, 대신 패턴의 해시 값와 현재 부분문자열의 해시 값을 비교한다.그리고 해시 값이 매칭되면, 패턴이 맞는 것이다.Rabin-Karp 알고리즘은 다음의 해시 값들을 계산할 필요가 있다:패턴의 해시 값더미 문자열(haystack)에서의 길이가 m인 모든 부분문자열해시 값은 문자열에서 패턴을 찾는 데 효율적으로 사용된다.해시 값은 rolling hash function으로 계산되는데, 기존의 글자를 하나 버리고 새 글자를 가져오면서 해시 값을 업데이트하면 된다.롤링 해시 함수의 과정은 다음과 같다:기저 수 b와..
컴퓨터과학/알고리즘 2024. 9. 20. 20:37
이전 Prev 1 Next 다음