Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 롤링 해시(Rolling Hash) 프로그램

롤링 해시(Rolling Hash)는 입력값 위를 이동하는 윈도우(window) 단위로 데이터를 해싱하는 해시 함수입니다. 윈도우가 한 칸씩 밀릴 때마다 전체를 다시 계산하지 않고 이전 해시 값을 재활용해 빠르게 갱신할 수 있다는 점이 가장 큰 특징입니다.

롤링 해시의 대표적인 응용 사례는 라빈-카프(Rabin-Karp) 문자열 검색 알고리즘입니다. Rabin과 Karp가 제안한 롤링 해시 함수는 문자열을 하나의 정수 값으로 변환하며, 이 정수 값은 곧 해당 문자열의 수치적 표현이 됩니다.

라빈-카프 알고리즘은 곱셈과 덧셈만으로 구성된 매우 단순한 롤링 해시 함수를 사용해 설명되곤 합니다.

H = c1ak-1 + c2ak-2 + … + cka0

여기서 a는 상수이며, c1, c2, …, ck는 입력 문자열의 각 문자에 해당합니다. H 값이 길이가 긴 문자열에서 매우 커질 수 있으므로, mod n 연산을 적용해 값을 일정 범위 안으로 유지합니다.

알고리즘

시작
    정수형 상수 변수 P_B를 선언하고 227로 초기화한다.
    정수형 상수 변수 P_M을 선언하고 1000005로 초기화한다.
    hash() 함수를 선언한다.
        문자열 s를 매개변수로 받는다.
        정수형 변수 r을 선언하고 0으로 초기화한다.
        for (int i = 0; i < s.size(); i++)
            r = r * P_B + s[i]
            r %= P_M
        r을 반환한다.
    rabin_karp(const string& n, const string& hstack) 함수를 선언한다.
        정수형 변수 h1을 선언하고 hash(n)으로 초기화한다.
        정수형 변수 h2를 선언하고 0으로 초기화한다.
        정수형 변수 power를 선언하고 1로 초기화한다.
        for (int i = 0; i < n.size(); i++)
            power = (power * P_B) % P_M
        for (int i = 0; i < hstack.size(); i++)
            h2 = h2 * P_B + hstack[i]
            h2 %= P_M
            if (i >= n.size())
                h2 -= power * hstack[i - n.size()] % P_M
                if (h2 < 0)
                    h2 += P_M
            if (i >= n.size() - 1 && h1 == h2)
                return i - (n.size() - 1)
        -1을 반환한다.
    문자열 변수 s1과 s2를 선언한다.
    "입력 문자열을 입력하세요:"를 출력한다.
    getline(line, s1)을 호출해 문자열을 입력받는다.
    "찾을 문자열을 입력하세요:"를 출력한다.
    s2를 입력받는다.
    if (rabin_karp(s2, s1) == -1)
        "문자열을 찾을 수 없습니다"를 출력한다.
    else
        문자열이 발견된 위치를 출력한다.
종료

핵심 아이디어는 다음과 같습니다. 먼저 찾으려는 패턴 문자열 n의 해시 값(h1)을 미리 계산해 둡니다. 그다음 대상 문자열(hstack)을 처음부터 순회하면서 현재 윈도우의 해시 값(h2)을 구하고, 윈도우가 이동할 때는 가장 앞의 문자 기여분을 빼고 새로 들어온 문자를 더하는 방식으로 해시를 갱신합니다. 두 해시 값이 일치하면 해당 위치를 패턴의 시작 위치로 반환합니다.

예제 코드

#include <iostream>
#include <string>
using namespace std;
const int P_B = 227;
const int P_M = 1000005;
int hash(const string& s) {
    int r = 0;
    for (int i = 0; i < s.size(); i++) {
        r = r * P_B + s[i];
        r %= P_M;
    }
    return r;
}
int rabin_karp(const string& n, const string& hstack) {
    int h1 = hash(n);
    int h2 = 0;
    int power = 1;
    for (int i = 0; i < n.size(); i++)
        power = (power * P_B) % P_M;
    for (int i = 0; i < hstack.size(); i++) {
        h2 = h2 * P_B + hstack[i];
        h2 %= P_M;
        if (i >= n.size()) {
            h2 -= power * hstack[i - n.size()] % P_M;
            if (h2 < 0)
                h2 += P_M;
        }
        if (i >= n.size() - 1 && h1 == h2)
            return i - (n.size() - 1);
    }
    return -1;
}
int main() {
    string s1, s2;
    cout << "Enter Input String: ";
    getline(cin, s1);
    cout << "Enter String to find: ";
    cin >> s2;
    if (rabin_karp(s2, s1) == -1)
        cout << "String not found" << endl;
    else
        cout << "String" << " " << s2 << " found at position " << rabin_karp(s2, s1) << endl;
    return 0;
}

실행 결과

Enter Input String: Tutorialspoint
Enter String to find: a
String a found at position 6

Enter Input String: Tutorialspoint
Enter String to find: b
String not found

첫 번째 실행에서는 "Tutorialspoint" 문자열에서 문자 'a'가 6번째 위치(인덱스 기준)에서 발견되었습니다. 반면 두 번째 실행에서는 존재하지 않는 문자 'b'를 찾았기 때문에 "String not found"가 출력됩니다. 이처럼 라빈-카프 알고리즘은 평균적으로 O(n + m)의 시간 복잡도로 문자열 검색을 수행할 수 있어, 긴 텍스트에서 패턴을 반복적으로 찾아야 하는 상황에서 특히 유용합니다.