[18-알고리즘] 문자열 탐색(String Match) 라빈 카프 알고리즘(Rabin-Karp algorigm)

앞의 포스팅에서 가장 무식한 방법인 Naive string match를 살펴 보았다. 패턴이 문자열애서 어디있는지 찾기 위해서 앞에서 부터 차례대로 찾는 방법이었습니다. 이렇게 무식한 방법보다 비용이 적게 들면서 빠르게 찾을 수 있는 방법인 라빈 카프 알고리즘을 살펴 보겠습니다. 텍스트 2359023141526739921이 있다고 합시다.(숫자로 구성되어있지만, 이는 문자열로 봅니다.) 여기서 패턴 문자열 31415를 찾으려고합니다. 텍스트 2359023141526739921에 패턴 문자열 31415가 있는지 확인하려고 합니다. 패턴 문자수는 '3', '1', '4', '1', '5' 즉 5개이다. 텍스트를 5개씩 앞에서 숫자로 변형시킬 것입니다. 라빈 카프 알고리즘의 핵심은 문자를 숫자 비교 문제로 바..

원문링크 : [18-알고리즘] 문자열 탐색(String Match) 라빈 카프 알고리즘(Rabin-Karp algorigm)