라빈카프 문자열 탐색 알고리즘(Rabin Karp string search algorithm)

뭔가 이름이 멋있는 알고리즘이다.

 

O(N + M)의 시간 복잡도
특정한 상황에서 KMP 알고리즘보다 매우 느리게 동작한다고 한다.

사실 그럴만도 한 것이 일단 hash함수를 써야하고, hash값이 같은 부분이 많으면 check하는 함수를 써야하니...

 

그래도 내 머리보단 빠르지 않을까?

 

설명은 이 분의 블로그가 좋겠다.

blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240679247&redirect=Dlog&widgetTypeCall=true&directAccess=false

 

#include <stdio.h>
#include <string.h>

char * parent = "acabacdabac";
char * pattern = "abacdab";

// 같은 문장인지 확인하는 함수
void check(char * parent, char * pattern, int start){
	int found = 1;
	int patternSize = strlen(pattern);
	for(int i = 0; i < patternSize; i++){
		if(parent[start + i] != pattern[i]){ found = 0; break; } // 완전 일치하면 break가 안된다
	}
	if(found){ printf("matched in index %d\n", start + 1); }
}

//문자열의 해쉬값 예시
// “abacdab” = 97 ∗ 2^6 + 98 ∗ 2^5 + 97 ∗ 2^4 + 99 ∗ 2^3 + 100 ∗ 2^2 + 97 ∗ 2^1 + 98 ∗ 2^0
//다음 해시 값 = 2 * (현재 해시 값 – 가장 앞에 있는 문자의 수치) + 새 문자의 수치

// 라빈카프 알고리즘
void rabinKarp(char * parent, char * pattern){
	int parentSize = strlen(parent);
	int patternSize = strlen(pattern);
	int parentHash = 0, patternHash = 0, power = 1;
	
	for(int i = 0; i <= patternSize; i++){
		if(i == 0){
			for(int j = 0; j < patternSize; j++){ // 초기 해쉬값 구하기
				//patternSize - 1이 마지막 문자의 위치다.
				parentHash = parentHash + parent[patternSize - 1 - j] * power;
				patternHash = patternHash + pattern[patternSize - 1 - j] * power;
				if(j < patternSize - 1) power = power * 2;
			}
		}
		// 초기값 이후는 recursion eqn으로 update
		// i - 1 가장 맨앞 index
		// i는 새로 update된 것
		else{ parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i]; }
		if(parentHash == patternHash) check(parent, pattern, i);
	}
}

int main(){
	rabinKarp(parent, pattern);
	
	return 0;
}