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

라빈 카프 알고리즘이란?

특이한 문자열 알고리즘이다.

항상 빠르지는 않지만 일반적인 경우 빠르게, 작동하는 간단한 구조의 문자열 알고리즘이다.

해시기법을 사용한다. 해시 기법은 긴 데이터를 그것을 상징하는 짧은 데이터로 바꿔주는 기법이다.

각 문자의 아스키 코드 값에 2의 제곱수를 차례로 곱하여 각각 더해주는 것이다. 서로 다른 문자열의 경우 일반적으로 해시 값이 다르게 나온다.

물론, 다른 문자열이지만, 해시 값이 같을 수도 있는데, 이 경우를 충돌(collision)이라고 한다. 그러나 확률이 매우 낮으므로, 무시한다.

원리

라빈 카프 알고리즘은, 여러 개의 문자열을 비교할 때, 해시 값을 구해서 비교하고, 전체 문자열과, 부분 문자열의 해시 값이 일치하는 경우에만, 문자열을 재검사해서 정확히 일치하는 지 확인한다.

구현

시간복잡도: O(N) -> 해시 값을 구할 때, 처음 한번 구해놓으면, 다음 해시값을 구할 때는 가장 처음값을 해시값에서 빼주고, 새로 추가된 부분을 해시값에 더해주기만 하면되기 때문

즉 수식은 긴 글 해시값 = 2 * (이전 긴 글 해시값 - 가장 앞의 수) + 새로 추가된 문자의 해시값 이다. 2를 곱해주는 이유는 자리수가 한칸 씩 밀리기 때문이다.

#include <iostream>

using namespace std;

void findString(string parent, string pattern) {
    int parentSize = parent.size(); // 전체 긴 글 사이즈 
    int patternSize = pattern.size(); // 찾아야하는 부분 문자열 사이즈 

    int parentHash = 0, patternHash = 0; // 각각 hash 값 초기화
    int power = 1; // 제곱수를 의미(처음은 2의0승)

    for(int i=0;i<=parentSize-patternSize;i++) {
        // 제일 처음 초기화 
        if(i==0) {
            for(int j=0;j<patternSize;j++) {
                parentHash += parent[patternSize - 1 - j] * power;
                patternHash += pattern[patternSize - 1 - j] * power;

                // 패턴 문자열의 사이즈 보다 j가 작다면 2씩 곱해주라는 뜻 
                if(j<patternSize-1) {
                    power *= 2;
                    //power *= 403; // MOD(나머지 연산)
                }
            }
        } else {
            // 긴 글 해시값 = 2 * (이전 긴 글 해시값 - 가장 앞의 수) + 새로 추가된 문자의 해시값
            parentHash = 2 * (parentHash - parent[i-1] * power) + parent[patternSize - 1 + i];

            // MOD(나머지연산)
            // parentHash = 403 * (parentHash - parent[i-1] * power) + parent[patternSize - 1 + i];
        }

        if(parentHash == patternHash) {
            bool finded = true;
            for(int j=0;j<patternSize;j++) {
                if(parent[i+j]!=pattern[j]) {
                    finded = false;
                    break;
                }
            }
            if(finded) {
                printf("%d번 째에서 발견했습니다\n", i+1);
            }
        }
        //printf("해시 값 비교: %d %d\n", parentHash, patternHash);
    }
}

int main(void) {
    string parent = "ababacabacaabacaaba";
    string pattern = "abacaaba";

    findString(parent, pattern);

    return 0;
}

reference: https://blog.naver.com/ndb796/221240679247