라빈 카프(Rabin-Karp)알고리즘

일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이다.

 

라빈 카프알고리즘의 특징 중 해시를 사용한다는 것이다.

 

여기서 해시를 알고가야하는데,

해시는 일반적으로 긴 데이터를 짧은 데이터로 바꿔주는 특징을 가지고 있다.

참고로 단순 해시 알고리즘의 경우는 연산 속도는 O(1) 달하고 있다.

 

라빈 카프 알고리즘은 문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘.

 

0. 각 문자의 아스키코드 값에 2의 제곱 수를 차례대로 곱하여 더해준다.

--> 이러한 경우에는 강한 충돌성을 보여준다.

충돌이 발생하면? 포인터를 이용해 연결 자료구조를 이용해 해결한다고 한다.

 

문자열을 시작 인덱스에서 한칸 한칸 옆으로 옮겨가며 해시값을 구하고, 패턴의 해시값을 비교한다.

--> 한칸 한칸 옆으로 옮겨가면서 해시값을 구하면 얼마나 오래걸릴까? 생각을 할 수 있다.

 

긴 글 해시 값 = 2 * (긴 글 해시 값 - 가장 앞에 있는 문자의 수치) + 새롭게 들어온 문자의 수치

 

#include <iostream>

using namespace std;

void findString(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++)
			{
				parentHash += parent[patternSize - 1 - j] * power;
				patternHash += pattern[patternSize - 1 - j] * power;
				if (j < patternSize - 1)
				{
					power *= 2;
				}
			}
		}
		else
		{
			parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i];
		}

		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(void)
{
	string parent = "ababacabacaabacaaba";
	string pattern = "abacaaba";

	findString(parent, pattern);

	return 0;
}