Rabin-Karp 알고리즘

 KMP 알고리즘과 더불어 문자열을 탐색하는 알고리즘 중 하나이다.

Rabin-Karp 알고리즘은 해싱을 이용해서 문자열을 비교하는 알고리즘으로,

최악의 경우 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가진다.

Rabin-Karp 알고리즘은 다음과 같이 진행된다.

- 패턴의 해시값을 계산한다.

- 비교하려는 문자열에서 패턴의 길이만큼 잘라서 해시값을 계산한다.

- 해시값을 비교한다. (해시값이 같다면 정확히 일치하는 것이고, 다르다면 첫글자를 빼주고 다음 글자를 추가한다.)

- (문자열 - 패턴)의 길이만큼 반복하고 종료한다.

예를 들어 패턴은 ABAC

문자열은 CABABACD라고 하면

패턴의 해시값을 다음과 같이 구한다.

static int cal(String pattern){
	int sum=0;
    int idx= pattern.length()-1;
    for(int i=0;i<pattern.length();i++){
    	sum+=pattern.charAt(i)*Math.pow(2,idx);
        idx--;
    }
    return sum;
}

즉 첫번째 자리부터 자리수에 따라 2의 n승을 곱해주고 더해주는 것이다.

위의 결과로 ABAC의 해시값은 981이 나온다.

이를 바탕으로 문자열 CABABACD와 비교하면 우선 패턴의 길이만큼 똑 떼서 비교한다.

CABA의 해시값은 993. 다르기 때문에 다음으로 진행한다.

이때 C는 탈락되고 B가 추가되니 C*(2^pattern.length()-1)값을 빼준다.

뺀 값에서 2를 곱해주고, B의 값을 더한다.

이를 통해 도출된 ABAB의 해시값은 980이 된다. 이를 반복하다가 ABAC가 되었을 때,

같은 값이 나오게 되고, 이는 패턴과 완전히 같다.

비교할 패턴이 작다면 이렇게 할 수 있지만 패턴의 크기가 굉장히 크다면 해시값이 무수히 커질 수 있다.

이때는 mod연산을 통해 도출할 수 있는데,

mod 연산을 실행한 경우에는 해시값이 유니크하지 않을 수 있기 때문에 

mod연산 후 해시값을 비교한 뒤, 해시값이 같다면 패턴과 해당 부분을 비교해서 일치 여부를 확인한다.

 

라고 이해했다.