Rabin-Karp1 Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾아주는 알고리즘입니다. 기본적인 아이디어는 (1)비교할 문자열과 패턴을 Hash function을 통해 해시값으로 변환하고, (2)해시값의 비교를 통해서 문자열이 일치하는지 확인하는데, 일치하지 않으면 다음 문자열로 넘어가고, 일치한다면 해당 문자열과 패턴의 1:1 매칭을 통해서 최종적으로 일치하는지 확인합니다. 즉, 해시값이 일치하면 문자열이 같다라고 판단할 수 있는데, 이는 해시 충돌(hash collison)이 없는 경우에 해당하긴 하지만 대부분 유효하다고 볼 수 있으며, 혹시나 해시값이 같지만 다른 문자열인 경우를 대비해서 해시값이 일치하는 경.. 2020. 12. 17. 이전 1 다음
