라빈-카프 알고리즘: 해시 기반 문자열 패턴 검색 완벽 정리

라빈-카프 알고리즘이란?

라빈-카프(Rabin-Karp) 알고리즘은 문자열 안에서 특정 패턴을 효율적으로 찾아내는 패턴 검색 알고리즘입니다. 이 알고리즘 역시 탐색 창(window)을 한 칸씩 이동하며 패턴을 검사하지만, 모든 경우에 전체 문자를 일일이 비교하지 않습니다. 대신 각 창의 해시 값을 미리 계산해 비교하고, 해시 값이 서로 일치할 때에만 실제 문자를 하나씩 대조합니다. 덕분에 불필요한 문자 비교가 크게 줄어들어 검색 효율이 향상됩니다.

시간 복잡도는 평균적으로 O(m+n)이며, 최악의 경우에는 O(mn)입니다. 최악의 경우는 해시 충돌(hash collision)이 계속 발생해 결국 매번 문자 단위 비교를 수행하게 되는 상황에서 나타납니다.

입력과 출력

입력:
메인 문자열: "ABAAABCDBBABCDDEBCABC", 패턴: "ABC"

출력:
패턴이 발견된 위치: 4
패턴이 발견된 위치: 10
패턴이 발견된 위치: 18

알고리즘

rabinKarpSearch(text, pattern, prime)

입력 − 메인 텍스트와 패턴, 그리고 해시 위치 계산에 사용할 소수(prime)

출력 − 패턴이 발견된 위치

시작
   patLen := 패턴의 길이
   strLen := 문자열의 길이
   patHash := 0, strHash := 0, h := 1
   maxChar := 문자 집합의 전체 문자 수

   패턴의 모든 문자 인덱스 i에 대해 반복
      h := (h * maxChar) mod prime
   종료

   패턴의 모든 문자 인덱스 i에 대해 반복
      patHash := (maxChar * patHash + pattern[i]) mod prime
      strHash := (maxChar * strHash + text[i]) mod prime
   종료

   i := 0 부터 (strLen - patLen) 까지 반복
      만약 patHash = strHash 이면
         charIndex := 0 부터 (patLen - 1) 까지 반복
            만약 text[i+charIndex] ≠ pattern[charIndex] 이면
               반복문 탈출
         종료

         만약 charIndex = patLen 이면
            위치 i에서 패턴이 발견되었음을 출력
      만약 i < (strLen - patLen) 이면
         strHash := (maxChar * (strHash - text[i]*h) + text[i+patLen]) mod prime
         만약 strHash < 0 이면
            strHash := strHash + prime
   종료
끝

동작 원리의 핵심: 롤링 해시

라빈-카프 알고리즘의 성능을 좌우하는 것은 롤링 해시(rolling hash) 기법입니다. 창이 오른쪽으로 한 칸 이동할 때 전체 해시를 처음부터 다시 계산하는 대신, 이전 해시 값에서 맨 왼쪽 문자의 기여분을 빼고 새로 들어온 문자의 기여분을 더해 O(1) 시간에 갱신합니다. 또한 소수로 나머지 연산을 수행해 해시 값의 범위를 제한하고 충돌 확률을 낮춥니다. 연산 과정에서 해시 값이 음수가 될 경우 소수를 더해 양수로 보정하는 절차도 포함됩니다.

C++ 구현 예제

#include<iostream>
#define MAXCHAR 256
using namespace std;

void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int charIndex, pattHash = 0, strHash = 0, h = 1;

    for(int i = 0; i<patLen-1; i++) {
        h = (h*MAXCHAR) % prime;     // h = {d^(M-1)} mod prime 계산
    }

    for(int i = 0; i<patLen; i++) {
        pattHash = (MAXCHAR*pattHash + pattern[i]) % prime;   // 패턴의 해시 값
        strHash = (MAXCHAR*strHash + mainString[i]) % prime;  // 첫 번째 창의 해시 값
    }

    for(int i = 0; i<=(strLen-patLen); i++) {
        if(pattHash == strHash) {    // 해시 값이 같으면 문자 일치 여부 확인
            for(charIndex = 0; charIndex < patLen; charIndex++) {
                if(mainString[i+charIndex] != pattern[charIndex])
                    break;
            }

            if(charIndex == patLen) {    // 패턴을 찾은 경우
                (*index)++;
                array[(*index)] = i;
            }
        }

        if(i < (strLen-patLen)) {    // 다음 창의 해시 값 계산
            strHash = (MAXCHAR*(strHash - mainString[i]*h) + mainString[i+patLen])%prime;
            if(strHash < 0) {
                strHash += prime;    // 해시 값이 음수이면 양수로 보정
            }
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int prime = 101;
    int index = -1;
    rabinKarpSearch(mainString, pattern, prime, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "패턴이 발견된 위치: " << locArray[i]<<endl;
    }
}

실행 결과

패턴이 발견된 위치: 4
패턴이 발견된 위치: 10
패턴이 발견된 위치: 18

주요 활용 분야

라빈-카프 알고리즘은 단순한 문자열 검색을 넘어 표절 검사 시스템, 디지털 포렌식, 악성코드 탐지처럼 여러 패턴을 동시에 찾아야 하는 다중 패턴 검색 환경에서 특히 유용합니다. 해시 값을 비교하는 구조 덕분에 여러 패턴의 해시를 미리 계산해 두면 텍스트를 한 번만 순회하면서도 여러 패턴을 동시에 검사할 수 있기 때문입니다.