Rabin-Karp [c++]

 Rabin-Karp 알고리즘은 항상 빠르지는 않지만 일반적으로 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이라는 점에서 자주 사용된다.

 

Ⅰ. 라빈카프 알고리즘은 해시(Hash) 기법을 사용하여 연산속도가 O(1) 이라는 장점이 있다. (시간복잡도는 O(n)

cf) 해시는 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법

ex) abaca의 해시 값 = 97 * 2^4 + 98 * 2^3 + 97 * 2^2 + 99 * 2^1 + 97 * 2^0

Ⅱ. 해시값이 중복되는 경우(==collision) 포인터를 이용해 연결자료 구조를 이용해 해결한다.

Ⅲ. 해시값은 거의 일치하는 일이 없기 때문에 'parent string'과 'pattern string'의 해시값이 일치하는 경우에만 문자열을 재검사 하여 정확히 일치하는지 확인한다.

 

parent Hash = 2 * (parent Hash -parent의 가장 앞에있는 문자의 수치) + 새롭게 들어온 문자의 수치

위와같은 식을 사용하면 매우 빠르게 연산을 처리할 수 있다.

 

 

#include <iostream>

using namespace std;

void rabinKarp(string parent, string pattern) {
int parentSize = parent.size();
int patternSize = pattern.size();
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++) { // parent를 pattenSize 만큼씩 Hash 값으로비교하기 위함
parentHash = parentHash + parent[patternSize - 1 - j] * power;
patternHash = patternHash + pattern[patternSize - 1 - j] * power;
power *= 2;
}
}
else { // i가 0이 아니라면 i번째 해쉬값 빼고 2를 곱한것에 i + patternSize -1번째 값을 해쉬값으로 변환하여 더함
parentHash = 2 * (parentHash - parent[i - 1] * (power / 2)) + parent[i + patternSize - 1];
}

if (parentHash == patternHash) { // 두 해쉬값이 일치한다면 상세비교 (해쉬값이 같아도 문자열이 다를 수 있으므로)
bool finished = true;
for (int j = 0; j < patternSize; j++) {
if (parent[j + i] != pattern[j]) { // 문자열이 다르면
finished = false;
break;
}
}
if (finished) cout << i + 1 << "번째에서 발견했습니다." << endl;
}
}
}



int main() {
string parent = "ababacabacaabacaaba";
string pattern = "abacaaba";
rabinKarp(parent, pattern);
return 0;
}