[Algorithm] Rabin-Karp Algorithm (라빈-카프 알고르짐)

Rabin-Karp Algorithm은 hasing을 사용해 텍스트의 패턴 문자열 집합 중 중 하나를 찾는 문자열 검색 알고리즘이다. 1987년 마이클 라빈(Michael Rabin)과 Richard Karp(리차드 카프)가 개발했다. 이 알고리즘의 핵심 아이디어는 검색하려는 패턴의 해시값을 계산한 다음 이 해시를 패턴과 길이가 같은 텍스트의 하위 문자열의 해시값과 비교하는 것이다. 이 방법을 사용하면 패턴과 일치할 가능성이 없는 텍스트의 많은 부분을 빠르게 건너뛸 수 있기 때문에 특히 패턴이 텍스트보다 훨씬 작은 경우 검색의 속도를 크게 높일 수 있다. 알고리즘의 개요는 아래와 같다. 해시 함수 : 각 문자열을 숫자 값으로 변환하는 해시 함수를 선택한다. 초기 해시 값 : 길이가 m인 패턴 P의 해시값..
기술(Tech, IT)/알고리즘(Algorithm) 2024. 4. 4. 00:38
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형