라빈-카프 알고리즘 (Rabin-Karp)
라빈-카프 알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘입니다. 간단하게 해시 값을 만들려면 문자열의 각 문자(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);
}
시간 복잡도 : O(N)
라빈-카프 알고리즘의 시간 복잡도는 문자열 길이(N) 만큼의 복잡도를 가집니다.
* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.