라빈 카프 알고리즘

라빈 카프 알고리즘

라빈 카프 알고리즘은 문자열 매칭 알고리즘입니다.

상당히 빠른 속도로 패턴을 찾을 수 있고 굉장히 재미있는 방식으로 패턴을 찾는다는 특징이 있습니다.

 

그 방식은 패턴의 해시값을 구한 다음, 패턴의 해시값과

현재 탐색중인 문자열의 해시값을 비교하여 탐색하는 방법을 사용합니다.

 

해시값을 만드는 과정

abcd라는 문자열이 있을때

i = d의 아스키코드값 * 2^0

j = c의 아스키코드값 * 2^1

k = b의 아스키코드값 * 2^2

l = a의 아스키코드값 * 2^3

abcd의 해시값 = i + j + k + l

 

다음에 탐색할 문자열의 해시값 구하기

[abcd]efg -> a[bcde]fg

(이전 해시값 - 가장 앞에있는 문자의 아스키코드 * 2^(문자열길이 - 1)) * 2

+ 다음에올 문자의 아스키코드 값

 

위의 방식으로 해시값을 구했다면 해시값 비교후에

실제로 찾은게 맞은지 한번 체크를 해주면 문자열 매칭 끝!

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int strHash;
int pattHash;
int sqr;

void makeHash(string str, string pattern)
{
	strHash = 0;
	pattHash = 0;
	sqr = 1;

	for (int i = pattern.size() - 1; i >= 0; i--)
	{
		strHash += str[i] * sqr;
		pattHash += pattern[i] * sqr;
		sqr *= 2;
	}
	sqr /= 2;

	return;
}

void findString(string str, string pattern)
{
	makeHash(str, pattern);

	for (int i = 0; i < str.size() - pattern.size() + 1; i++)
	{
		if (strHash == pattHash)
		{
			bool finded = true;
			for (int j = 0; j < pattern.size(); j++)
			{
				if (pattern[j] != str[j]) finded = false;
			}

			cout << i + 1 << "번째에서 발견" << "\n";
		}
		int frontHashValue = str[i] * sqr;
		strHash = ((strHash - frontHashValue) << 1) + str[i + pattern.size() ];
	}
}

int main()
{
	string str = "qpwoeiruqpwoeiruqpwoeiru";
	string pattern = "qpwoeir";
	findString(str, pattern);
	return 0;
}