#11 라빈 카프 문자열 매칭

라빈 카프 문자열 매칭

-아스키 코드 기반의 해시함수(Hash Function)을 이용해 특정한 문자열에 대한 해시 값을 구한다.

-'연속적인 문자열이 이어지는' 상황이므로 해시함수의 동작에 있어서 연산 속도가 O(1)이다.

 

 

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

-라빈 카프 문자열 매칭 알고리즘에서 해시 함수는 '각 문자의 아스키 코드 값에 2의 제곱 수를 차례대로 곱해 더한 값'을 구한다.

-일반적으로 서로 다른 문자열의 경우 해시 값이 다르게 나온다.

해시 함수에 기반한다는 점에서 해시 충돌에 대한 처리가 필요하다.

(해시 함수(hash function) 또는 해시 알고리즘 또는 해시함수알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.)

 

ex)  문자열: “bbacdab”
= 𝟗𝟖 ∗ 2^6 + 98 ∗ 2^5 + 97 ∗ 2^4 + 99 ∗ 2^3 + 100 ∗ 2^2 + 97 ∗ 2^1 + 98 ∗ 2^0
= 12,444

 

라빈 카프 문자열 매칭 알고리즘에서는 해시  충돌을 감안해야 한다는 점에서 부분 문자열의 해시 값이 일치하는 경우에만 문자열을 재검사한다.

 

라빈 카프 문자열 매칭: 해시 함수의 반복적 계산
-해시 함수를 반복적으로 계산할 때는 ‘문자열이 이어져 있다는 특징’을 이용하여 빠르게 계산한다.
해시 값: 12,398
다음 해시 값 = 2 * (현재 해시 값 – 가장 앞에 있는 문자의 수치) + 새 문자의 수치

 

코드 예시

#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);
	}
}

//라빈 카프 알고리즘 구현
void rabinKarp(char* parent, char* pattern) {
	int parentSize = strlen(parent);
	int patternSize = strlen(pattern);
	int parentHash = 0, patternHash = 0, 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);
		}
	}
}
//사용
int main(void) {
	rabinKarp(parent, pattern);
	system("pause");
}

 

결과 값