Rabin Karp (라빈 카프) 알고리즘

Rabin-Karp 알고리즘은 해싱(Hashing)을 사용해서

문자열에서 특정 패턴을 찾아주는 알고리즘 입니다.

---

Pattern에서 Target을 찾는 문제

길이가 더 긴 Pattern = "abacbaacb" 에서

길이가 더 짧은 Target = "acb" 를 찾는 문제가 있습니다.

 

문자열에 hash 값을 부여한 뒤,

그 hash 값으로 문자열을 판별하면 됩니다.

---

해시 함수

해시 함수로는 Rabin fingerprint를 많이 사용합니다.

각 문자에 m 거듭제곱을 곱해서 다 더한 값이 hash 값이 됩니다.

 

Example)

먼저, Target의 hash 값을 구하겠습니다.

거듭제곱으로 사용할 m은 2로 가정했습니다.

 

이후 Pattern에서 Target의 길이만큼 잘라서 hash 값을 비교해주면 됩니다.

 

hash(Target) = 684,

hash(Pattern) = 681

hash 값이 다르므로 문자열이 다르다고 판단할 수 있습니다.

 

2번째 문자열 역시 hash(Target) 값과 다릅니다.

 

3번째 문자열은 hash 값이 hash(Target)과 동일합니다.

그리고 문자열을 확인해보니 문자열 역시 똑같습니다.

---

hash 값 빠르게 구하기

Pattern의 문자열 길이를 N,

Target의 문자열 길이를 M 이라고 둔다면

 

Target과 문자열이 같은지 비교해야 하는 문자열의 개수는 : N - M - 1개 입니다.

hash 값을 계산하는 시간 복잡도는 O(M) 입니다.

=> O(N * M)

 

N과 M이 10만 정도 되면 시간 내에 돌리기 어렵습니다.

 

더 빠른 방법을 찾아봐야 합니다.

Pattern에서 hash값을 구한 모습입니다.

 

1번째 문자열과 2번째 문자열의 차이는 문자 2개 뿐입니다.

그리고 이를 제외한 공통 부분은 M배 만큼 차이가 납니다.

즉, new_hash = (old_hash - 첫번째 글자 * M^m) * M + 새로운 글자 입니다.

 

처음 hash 값만 O(M)만에 구해준 뒤,

남은 hash 값 계산은 O(1) 만에 계산이 가능합니다.

결과적으로 O(N) 이 됩니다.

---

hash 값 충돌?

hash 값이 같다고 무조건 같은 문자열은 아닙니다.

 

M=2라고 가정했을 때,

acb = 97 * 4 + 99 * 2 + 98 = 684

abd = 97 * 4 + 98 * 2 + 100 = 684

다른 문자열이지만, 같은 hash 값이 나올 수 있습니다.

 

hash 값이 같아도 문자열이 진짜 같은지 판별하는 과정이 필요합니다.

단순하게 반복문으로 문자열의 시작부터 끝까지 비교해주면 됩니다.

bool TOF(char* s1, char* s2) {
	for (int i = 0; s1[i]; ++i) {
		if (s1[i] != s2[i]) return false;
	}

	return true;
}

 

+) M 값을 더 늘리면 충돌이 안 일어나지 않을까?

 

문자 구성이 알파벳 소문자로만 이루어져 있다고 한다면, 

알파벳 소문자 개수인 26개보다 큰 수로 M을 설정하면 충돌이 안 일어납니다.

 

하지만, 문자열이 길어지면 거듭 제곱을 곱하는 과정에서 overflow가 일어납니다.

큰 수에 임의의 수를 modular 취해줘야 하기 때문에 어쩔 수 없이 겹치는 수가 발생합니다.

---

Modular

문자열이 길이가 길어지거나,

거듭 제곱할 M의 값이 2가 아닌 더 큰 수로 설정해두면,

int나 long long의 범위를 넘어서는 문제가 발생합니다.

 

이를 modular를 씌워서 해결해야 하는데 modular는 아래와 같이 결과값이 나올 수 있습니다.

• 양수 % mod = T (양수)
• 음수 % mod = -K (음수)

Rabin-Karp 알고리즘으로 hash 값을 계산하다보면 음수가 나올 수 있습니다.

(modular를 취하고 첫번째 문자를 빼는 과정)

 

하지만, Pattern에서 Target의 문자열 길이만큼 Rabin-Karp로 hash를 추출한다면 무조건 양수가 나와야 합니다.

(더하는 과정 밖에 없기 때문)

 

그래서 음수 % mod 에서 음수가 나오면 제대로 판단할 수 없게됩니다.

 

c++ 컴파일러 기준으로 음수를 modular 취하면 아래와 같이 나옵니다.

#include <cstdio>

int main()
{
	printf("%d\n", -7 % 10); // -7
}

이를 Rabin-Karp에 맞게 양수로 바꿔주려면 어떻게 해야할까요?

 

모듈러 만큼 공간이 있다고 가정해보겠습니다.

그럼 10칸이 있습니다.

 

-7로 7칸을 먹었기 때문에 남은 3칸을 반환해주면 됩니다.

 

=> (N % M + M) % M

(-7 % 10 + 10) % 10

---

코드

M : 2가 아닌, 5381로 설정했습니다.

적당히 큰 소수로 설정하면 충돌 가능성이 현저히 줄어듭니다.

inline int Mod(ll x) {
	x %= mod;
	if (x < 0) x += mod;
	return x;
}

bool TOF(int idx) {
	for (int i = 0; P[i]; ++i) {
		if (P[i] != T[idx + i]) return false;
	}

	return true;
}

int solve() {
	int ret = 0, pow = 1, key = 0, cmp = 0;
	int len = strlen(P);

	for (int i = 0; i < len; i++) {
		key = Mod((ll)key * 5381);
		key = Mod(key + P[i]);

		cmp = Mod((ll)cmp * 5381);
		cmp = Mod(cmp + T[i]);

		if (i != len - 1) pow = Mod((ll)pow * 5381);
	}

	for (int i = len - 1; T[i]; i++) {
		if (key == cmp) {
			if(TOF(i - len + 1)) res[ret++] = i - len + 1;
		}
		cmp = Mod((ll)cmp - (ll)pow * T[i - len + 1]);
		cmp = Mod((ll)cmp * 5381);
		cmp = Mod(cmp + T[i + 1]);
	}

	return ret;
}

---

문제

https://www.acmicpc.net/problem/3033

3033번: 가장 긴 문자열

https://www.acmicpc.net/problem/17228

17228번: 아름다운 만영로

 

감사합니다.