문자열 패턴 검색: 2 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm)

설명

Naive 패턴 검색에서는, 우리는 모든 pattern의 길이와 같은 부분문자열들을 원본 문자열에서 추출해서 각각 한 글자씩 비교했다.

 

Rabin-Karp 알고리즘에서도, 모든 부분문자열을 검사하지만, 대신 패턴의 해시 값와 현재 부분문자열의 해시 값을 비교한다.

그리고 해시 값이 매칭되면, 패턴이 맞는 것이다.

Rabin-Karp 알고리즘은 다음의 해시 값들을 계산할 필요가 있다:

• 패턴의 해시 값
• 더미 문자열(haystack)에서의 길이가 m인 모든 부분문자열

해시 값은 문자열에서 패턴을 찾는 데 효율적으로 사용된다.

해시 값은 rolling hash function으로 계산되는데, 기존의 글자를 하나 버리고 새 글자를 가져오면서 해시 값을 업데이트하면 된다.

롤링 해시 함수의 과정은 다음과 같다:

1. 기저 수 b와 모듈러 수를 정한다. b는 문자 집합의 크기이다. (ASCII의 경우 256)
   b를 쓰는 이유는 각 문자의 고유한 값을 위해서이다.
   모듈러 수는 해시 값의 오버플로우 제한을 위해서 쓰인다.
2. 해시 값을 초기화해라. 첫 해시 값을 0으로 둔다.
3. 패턴 문자열의 초기 해시 값을 구하라.
   왼쪽으로 오른쪽으로 순회하면서, 각 글자 'c'는 인덱스 'i'와 다음과 같이 계산되어서 해시 값에 누적된다:
   c * (b^{m-i-1}) % p (m : 패턴 문자열의 길이)
4. 패턴과 같은 길이의 첫 부분 부분문자열을 계산하는 걸로 시작해라.
5. 각각의 연속적인 부분문자열에 대해, 해시 값을 업데이트한다:
   패턴을 한 칸 오른쪽으로 옮기려면, 맨 왼쪽이 해시 값에 기여한 값을 없애고, 오른쪽 새 글자의 해시 값을 더한다
   i부터 i+번자리로 가는 데에 대한 식은 다음과 같다:
   hash = (hash - (text[i - m] * (b^{m-1})) % p * b + text[i])
6. 해시 값을 비교한다. 해시 값이 같으면, 가능성이 있는 것이다.
   해시 충돌이 일어날 수 있으므로, 주의해야 한다.

Rabin-Karp의 과정은 다음과 같다:

1. 패턴 문자열의 해시 값을 계산한다.
2. 문자열의 시작으로부터 다음을 반복한다:
   
   • 현재 위치에서 길이가 m인 부분문자열의 해시 값을 계산한다.
   • 만약 현재 해시와 패턴의 해시가 같으면, 부분문자열과 패턴 문자열을 비교한다.
   • 만약 부분문자열과 패턴 문자열이 같으면, 그 스타팅 인덱스의 값을 저장한다.

슬라이딩 윈도우를 민다고 생각하면 되겠다.

아래는 간단한 시각화이다.

 

코드(C++)

#include <iostream>

#define d 256

using namespace std;

void search(char pat[], char txt[], int q) {
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0; // hash for pattern
    int t = 0; // hash for text
    int h = 1;

    for (i = 0; i < M - 1; ++i) {
        h = (h * d) % q;
    }

    // initialize window..
    for (i = 0; i < M; ++i) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }

    for (i = 0; i <= N - M; ++i) {
        if(p == t) {
            for (j = 0; j < M; ++j) {
                if(txt[i + j] != pat[j]) {
                    break;
                }
            }

            if(j == M) {
                cout << "pattern found at: " << i << "\n";
            }
        }

        if(i < N-M) {
            t = (d * (t - txt[i] * h) + txt[i + M]) % q;
        }

        if(t < 0)
            t += q;
    }
}

int main() {
    char txt[] = "hello from hello world.cpp";
    char pat[] = "hello";

    int q = INT_MAX;

    search(pat, txt, q);
    return 0;
}

q의 값은 클 수록 좋다. 해시 충돌이 덜 일어나게 된다.

 

pattern found at: 0
pattern found at: 11

 

 

 

복잡도분석

시간복잡도는 일반적인 경우 및 최선의 경우에 O(n+m)이지만,

최악의 경우 O(nm)이다. 해시 값이 우연히 모두 일치하는 경우가 있다.

 

 

응용 - Rabin-Karp를 이용하여 팰린드롬 찾기

p_pow 배열: 해시 계산에 필요한 기저 수 p의 거듭제곱 값을 미리 저장함. p_pow[i]는 p의 i제곱.

h배열: 원본 문자열 s의 prefix 해시 값을 저장한다. h[i]는 0부터 i-1까지의 해시 값을 의미한다.

h_rev배열: 역문자열 rev_s의 prefix 해시 값을 저장한다. h_rev[i]는 rev_s의 0부터 i-1까지의 해시 값을 의미한다.

1. 패턴의 해시값을 미리 계산
   p_pow[i] = (p_pow[i-1] * p) % mod
2. 원본 문자열의 접두사 해시를 계산
   롤링 해시 함수를 이용하여, 원본 문자열 s의 접두사 해시 값을 배열 h에 저장한다.
   h[i+1] = (h[i] * p + (s[i] - 'a' + 1)) % mod로 계산한다.
3. 문자열 반전 및 prefix 해시 계산
   역 문자열 rev_s를 만든다. 그의 해시값을 h_rev에 저장한다.
4. 모든 substring에 대해서 검사
   substring의 길이 1부터 n까지 순회한다.
   i는 0부터 n-1까지 반복하는데, 그 안에서의 j는 i+l-1로 한다.
   부분문자열 s[i~j]의 해시 값을 계산한다.
   hash_s = (h[j+1] - (h[i] * p_pow[l])% mod + mod) % mod
   반전된 문자열의 부분문자열 rev_s[n-j-1, n-j-i +l-1]의 해시 값을 구한다.
   hash_rev_s = (h_rev[n-j-i+l] - (h_rev[n-j-1]*p_pow[l]) % mod + mod ) % mod
   
   둘의 해시가 같다면, s[i~n-j-1]는 팰린드롬이다.
   
   

코드(C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 1000000007;
const ll p = 31;

int main()
{
    string s = abcba
    int n = s.size();

    vector<ll> p_pow(n + 1);
    p_pow[0] = 1;
    for (int i = 1; i <= n; i++)
        p_pow[i] = (p_pow[i - 1] * p) % mod;

    vector<ll> h(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i + 1] = (h[i] * p + (s[i] - 'a' + 1)) % mod;

    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    vector<ll> h_rev(n + 1, 0);
    for (int i = 0; i < n; i++)
        h_rev[i + 1] = (h_rev[i] * p + (rev_s[i] - 'a' + 1)) % mod;

    int palindrome_count = 0;

    for (int l = 1; l <= n; l++)
    {
        for (int i = 0; i + l <= n; i++)
        {
            int j = i + l - 1;

            ll hash_s = (h[j + 1] - (h[i] * p_pow[l]) % mod + mod) % mod;

            int rev_i = n - j - 1;
            int rev_j = rev_i + l - 1;

            ll hash_rev_s = (h_rev[rev_j + 1] - (h_rev[rev_i] * p_pow[l]) % mod + mod) % mod;

            if (hash_s == hash_rev_s)
            {
                palindrome_count++;
                cout << s.substr(i, l) << "\n";
            }
        }
    }

    cout << "Total palindromic substrings: " << palindrome_count << endl;
    return 0;
}

출처

https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/?ref=shm