오버플로우

라빈-카프(Rabin-Karp) 알고리즘

1. 개념 ⚽ 라빈-카프(Rabin-Karp) 알고리즘이란 해싱(Hashing)을 이용한 문자열 매칭 알고리즘이다. 비교하고자 하는 문자들과 패턴의 문자들을 일일이 비교하는 대신에 문자열의 해시값을 비교하는 방식으로 진행된다. 2. 동작방식(연습용) 🏀 동작 방식은 아래와 같다. 해시 함수를 설정한다. 해시 함수를 이용하여 패턴의 해시값을 구한다. 비교하고자 하는 문자열의 해시값을 구한다. 일치하면 패턴과 찾은 문자열을 1:1 비교한다. 일치하지 않으면 비교하고자 하는 문자열을 한 칸 뒤로 옮겨서 3번부터 다시 시작한다. 해시값이 같더라도 1:1 매칭을 통해서 최종적으로 패턴과 비교하고자 하는 문자열이 일치하는지 확인하는 절차가 필요하다. 그 이유는 해시값이 같다고 해서 무조건 같은 문자열이라고 보장할 ..