[기본문제풀이] rabin karp 알고리즘

 

풀이 일시 : 2020-08-22

​

라빈카프 알고리즘 :

문자열 매칭 알고리즘으로 해시기법을 이용한다.

충돌하는 경우에는 포인터를 이용해 연결자료구조(link)를 이용해 해결한다.

​

문제 :

라빈카프 알고리즘을 이용하여 "ababacabacaabacaaba" 에서 "abacaaba"의 시작점을 찾아라

​

풀이 :

#include <iostream>
#include <string>

using namespace std;

void hashs(string parent, string pattern) {
	int parentHash=0, patternHash=0, power = 1;
	int parentSize = parent.size();
	int patternSize = pattern.size();
	for (int i = 0; i <= parentSize - patternSize; i++) {
		//처음 해쉬값 생성
		if (i == 0) {
			for (int j = 0; j < patternSize;j++) {
				//그냥 문자에다 곱하는것 = 즉 아스키코드값에 곱하는 것
				parentHash += parent[patternSize - 1 - j] * power;
				//7 6 5 4 3 2 1 0
				//7번째 문자에 * power(1) + 6번째문자에 *power(2)...
				patternHash += pattern[patternSize - 1 - j] * power;
				//패턴 문자열의 사이즈보다 j가 작다면 2씩 곱해줘라
				if (j < patternSize - 1) {
					power *= 2;
				}
			}
		}
		//이미 생성되었다면 parentHash만 바꿔주면된다.
        //parentHash를 계속바꿔주며 patternHash와 같은지 비교만 해주면 된다.
		//부모 해시값 = 2*(부모 해시값-가장앞에있는 문자의 수치)+새롭게 들어온 문자의 수치. 즉 글자 하나 해시값만 계속 바뀌는것
		else {
			parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i];
		}
		//해시가 일치한다면 find
		if (parentHash == patternHash) {
			bool finded = true; //해시값 확인
			for (int j = 0; j < patternSize; j++) {
				if (parent[i + j] != pattern[j]) { //문자 하나하나확인
					finded = false;
					break;
				}
			}
			if (finded) {
				printf("%d번째에서 발견했습니다.\n", i + 1);
			}
		}
	}
}



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