17. 라빈 카프 문자열 매칭

라빈 카프 문자열 매칭의 특징

• 해시(Hash)를 활용하는 알고리즘
• O(N+M)의 시간 복잡도를 가짐
• 아스키 코드 기반의 해시 함수(Hash Function)을 이용해 해시 값을 구함
• 연속적인 문자열이 이어지는 상황이므로 해시 함수 동작에 있어 연산 속도가 O(1)

라빈 카프 문자열 매칭 : 해시 함수

라빈 카프 문자열 매칭 알고리즘에서 해시 함수는 '각 문자의 아스키 코드 값에 2의 제곱 수를 차례대로 곱하여 더한 값'을 구한다. 일반적으로 서로 다른 문자열의 경우 해시 값이 다르게 나오며 해시 함수에 기반하기 때문에 해시 충돌에 대한 처리가 필요

해시 함수의 눈사태 효과

문자열 : "abacdab"

위와 같이 문자가 하나만 달라져도 값이 달라지는 눈사태 효과로 해시 값 또한 달라진다.

라빈 카프 문자열 매칭의 과정

라빈 카프 문자열 매칭 구현

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
#include <string.h>

char* parent = "acabacdabac";
char* pattern = "abacdab";

// 확인 함수
void check(char* parent, char* pattern, int start) {
    int found = 1;
    int patternSize = strlen(pattern);
    for (int i = 0;i < patternSize;i++) {
        if (parent[start + i] != pattern[i]) {
            found = 0;
            break;
        }
    }
    if (found) {
        printf("[인덱스 %d에서 매칭 발생]\n", start + 1);
    }
}

// RarbinKarp
void rabinKarp(char* parent, char* pattern) {
    int parentSize = strlen(parent);
    int patternSize = strlen(pattern);
    int parentHash = 0;
    int patternHash = 0;
    int power = 1;

    for (int i = 0;i < parentSize - patternSize;i++) {
        if (i == 0) {
            for (int j = 0;j < patternSize;j++) {
                parentHash = parentHash + parent[patternSize - 1 - j] * power;
                patternHash = patternHash + pattern[patternSize - 1 - j] * power;
                if (j < patternSize - 1) power = power * 2;
            }
        }
        else {
            parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i];
        }
        if (parentHash == patternHash) {
            check(parent, pattern, i);
        }
    }
}

// main
int main(void) {
    rabinKarp(parent, pattern);

    system("pause");
    return 0;
}

해시값이 일치할 때만 확인 함수 수행