라빈 카프 알고리즘

KMP관련 문제를 풀다가 라빈 카프 알고리즘이란 것이 있다는 것을 알았다.KMP알고리즘과 동일하게 문자열 매칭 알고리즘이다. 보통 KMP를 자주 쓰지만 그 못지 않게 꽤 빠르게 작동한다. 라빈 카프 알고리즘은 특이하게 해시를 사용한다. 해시의 장점의 경우 단순한 해시 알고리즘의 시간 복잡도는 O(1)이란 것이다. 지금까지 해시를 잘 사용하지 않았기 때문에 SWEA에서 해시 관련 문제들을 푸는데 어려움을 겪고 있다. 라빈 카프 알고리즘은 그렇게 어렵지 않으니 간단하게 설명하고 코드로 넘어가겠다.

 

간단한 예제로 abc를 들겠다. 이진수 변환하듯이 뒤에서부터 각 자릿수 제곱승 * 각 자리의 수자를 다 더하여주면

abc = a*2^2 + b*2^1 + c*2^0이런 식으로 해시 값으로 나타낼 수 있다. 만약 abcde에 abc라는 문자열이 있는지

확인하려면 먼저, abcde에서 확인하려는 문자열의 길이 만큼 해시 값을 구한다. 그 후 하나씩 하나씩 옆으로 가게 되는데 이때 bcd의 값을 구할 때 새로 구하는 것이 아닌 앞에서 사용한 abc의 값에다가 a*2^2를 빼고 전체에 2를 곱해준 다음 d*2^0을 더해준다. 그렇다면 b*2^2+c*2^1+d*2^0이라는 값을 가지고 확인하려는 문자열의 해시 값과 비교를 하면 된다. 더욱 자세한 것은 이 블로그를 보고 이해를 하였다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221240679247 

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

 

보통 라빈 카프를 사용할 때 곱하는 값이 매우 커지기 때문에 mod라는 특정 수를 지정하여 나머지를 사용하여 해시 값을 사용하던가 아니라면 long long을 사용하는 것을 추천한다.

 

#include<iostream>
#include<cstring>

typedef long long ll;

using namespace std;

char b[500001], s[100001];

int n, m;

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case;
	int T;

	cin >> T;

	int result;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> b >> s;
		result = 0;
		ll com[5] = { 0, };
		ll temp[5] = { 0, };
		ll mod[5] = { 1,1,1,1,1 };

		int s_len = strlen(s), b_len = strlen(b);
		int flag;
		for (int i = 0; i < b_len - s_len + 1; i++)
		{
			if (i == 0)
			{
				for (int j = 0; j < s_len; j++)
				{
					for (int x = 0; x < 5; x++)
					{
						com[x] += s[s_len - 1 - j] * mod[x];
						temp[x] += b[s_len - 1 - j] * mod[x];
					}
					if (j < s_len - 1)
						for (int x = 0; x < 5; x++)
							mod[x] *= (x + 1);
				}
			}
			else {
				for (int j = 0; j < 5; j++)
				{
					temp[j] = (j + 1) * (temp[j] - b[i - 1] * mod[j]) + b[s_len - 1 + i];
				}
			}
			flag = 1;
			for (int j = 0; j < 5; j++)
				if (temp[j] != com[j])
					flag = 0;
			if (flag)
				result++;
		}
		cout << "#" << test_case << " " << result << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}