In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an exact match of a pattern string in a text.

라빈 카프 알고리즘은 문자열 매칭에 활용되는 해시 알고리즘이다. 라빈씨랑 카프씨가 만들어서 라빈카프이다. 이 알고리즘은 해시함수 중 롤링 해시라는 기법을 사용한다.

KMP와 같은 알고리즘과 비교했을때 여러 개의 패턴을 한 번에 검색하는 데 유리하다.

개념

슬라이딩 윈도우 + 해싱을 활용한다.
1. 해시 함수를 사용해 패턴과 동일한 길이의 모든 서브 스트링에 대해 해시 값을 계산. (rolling hash기법 활용)
2. 두 해시 값이 일치하면 문자열을 직접 비교해서 패턴이 일치하는지 확인.

시간복잡도

시간복잡도 : 평균적으로 O(N) 해쉬충돌로 인한 최악의 상황은 O(M*N)
패턴의 길이 : M
텍스트의 길이 : N

Rolling hash

롤링 해쉬는 해쉬 함수의 일종이다. 새로운 서브스트링의 해시 값을 빠르게 계산하기 위해 라빈카프 알고리즘이 활용하는 기법이다. 물론 라빈 카프가 만든건 아니지만 대표적인 활용법이 라빈카프 알고리즘이다.

진법계산과 유사한 방식을 사용하며, 슬라이딩 윈도우처럼 이전 서브 스트링의 해시값을 활용해 다음 서브 스트링의 해시값을 계산한다.

c: 입력 알파벳
k: 패턴의 길이
a : 알파벳의 개수에 따른 상수

해시값을 이런 식으로 계산하게 되면, 바로 다음 서브 스트링의 해시값은 해당 값으로 O(1)에 구할 수 있다.

H_new = (H_old - c_1 * a ^ (k - 1)) * a + c_k+1

c_1 : 제거된 문자
c_k+1 : 주가된 문자

만약 rolling hash를 사용하지 않으면 O(M)의 시간이 소요된다.

이런 방식으로 문자 하나의 값이 다른 해쉬값을 상수시간에 구하는 최적화 응용이 가능하다.

구현

    private static int customHash(String s) {
        int code = 0;
        for (char c : s.toCharArray()) {
            code *= 27;
            code += c - 'a' + 1;
        }
        return code;
    }

System.out.println(customHash("abc"));

소문자만 입력으로 들어온다는 가정하에 알파벳의 개수는 26개이다. 여기서 문자열이 가변길이 일때 ab와 b를 구분해주기 위해서, a를 1로 잡아줄 필요가 있다. 자연스럽게 알파벳이 1~26을 이용하므로 27을 상수로 잡아주었다.

1 * 27^2 + 2 * 27 + 3 = 786

참고

https://en.wikipedia.org/wiki/Rabin–Karp_algorithm