라빈-카프 알고리즘 (Rabin-Karp) 해시값을 통한 문자열 비교

정의 / 시간 복잡도 O(n)

문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 된다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 된다.

 

예를 들어 ABCD와 ABED라는 문자열이 있을 때

ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618

ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624

이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 된다.

 

간혹 해시 값이 서로 충돌하는 해시 충돌 현상이 발생할 수도 있는데 가능성이 매우 낮지만 일치하는 경우 모듈러 연산(MOD)을 이용하여 오버플로우를 방지하고 정확하게 문자열 일치 여부를 결정한다.

원리

문자열 AABDCDABD에서 패턴 ABD가 발견되는 지 라빈-카프 알고리즘을 통해 탐색해보자

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(AAB) : 846

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 다르므로 탐색에 실패한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(ABD) : 851

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 같으므로 탐색에 성공한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(BDC) : 865

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 다르므로 탐색에 실패한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(DCD) : 881

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 다르므로 탐색에 실패한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(CDA) : 872

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 다르므로 탐색에 실패한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(DAB) : 873

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 다르므로 탐색에 실패한다.

검색 대상	A	A	B	D	C	D	A	B	D
패턴	A	B	D

검색 대상 문자열 해시 값(ABD) : 851

문자열 패턴 해시 값(ABD) : 851

두 해시 값이 같으므로 탐색에 성공한다.

 

검색 대상 문자열의 해시 값이 구해지는 원리는 지정한 수 * (검색 대상 문자열 해시 값 - 맨 앞의 문자열 값 * 지정한 수^제곱 수) + 새로 탐색된 문자열 값이다. 예를 들어 위 예시의 검색 대상 문자열에서 AAB의 해시 값은 846이다. 탐색에 실패하여 한칸 이동하여 ABD가 될 때 해시 값은 3 * ( 846 - 65 * 3^2 ) + 68 = 851이 된다. 3^2를 곱하는 이유는 문자열 패턴의 길이가 3자리이므로 제곱 수가 2가 되기 때문이다. 만약 문자열 패턴의 길이가 5자리라면 제곱 수는 4가 된다.

 

이러한 원리 때문에 라빈-카프 알고리즘은 문자열을 빠르게 탐색할 수 있는 알고리즘이다.

// Algorithm Analysis
// 라빈-카프 알고리즘 (Rabin-Karp)

#include <iostream>

using namespace std;

// ws : 검색 대상 문자열 , ps : 검색할 패턴 문자열
void findString(string ws, string ps) {
	int wsSize = ws.size();
	int psSize = ps.size();

	int wsHash = 0;
	int psHash = 0;
	int power = 1; // 제곱수

	for (int i = 0; i <= wsSize - psSize; i++) {
		if (i == 0) {
			for (int j = 0; j < psSize; j++) {
				wsHash += ws[psSize - 1 - j] * power;
				psHash += ps[psSize - 1 - j] * power;
				if (j < psSize - 1) power *= 3;
			}
		}
		else {
			wsHash = 3 * (wsHash - ws[i - 1] * power) + ws[psSize - 1 + i];
		}
		if (wsHash == psHash) {
			bool isFind = true;
			// 우연히 해시값이 겹친 경우 위해 문자열 일치 여부 검사
			for (int j = 0; j < psSize; j++) {
				if (ws[i + j] != ps[j]) {
					isFind = false;
					break;
				}
			}
			if (isFind) {
				cout << wsHash << " " << psHash << endl;
				printf("%d번째에서 발견\n", i + 1);
			}
		}
	}
}
int main() {
	string ws = "AABDCDABD";
	string ps = "ABD";
	findString(ws, ps);
}

출처 : [알고리즘] 라빈-카프 알고리즘 (Rabin-Karp) — yjglab (tistory.com)