문자열 매칭 알고리즘[1](라빈 카프)[String Searching Algorithm, Rabin-Karp]

문자열 S에서 패턴 P를 찾는다고 해보자.

기본적으로 생각나는 방법은 S의 시작 위치에서 P가 나오는지 검사하는 것이다.

s[0]부터 P와 같은지?,

s[1]부터 p와 같은지?,

s[2]부터 p와 같은지?,

...

 

이 경우에 시간복잡도는 O(|S|x|P|)이다.

일번적으로 비교할 경우 너무 비효율적이어서 사용하기 어렵다.

 

문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 

---

1. 라빈 카프 알고리즘 정의

해쉬(Hash)함수를 사용해서 문자열에서 특정 문자열과 일치하는지 찾아주는 알고리즘이다.

 

2. 라빈 카프 알고리즘의 개념

해쉬함수 : 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어주는 함수(어떤 문자열을 정수로 표현하는 함수)

 

라빈 카프 알고리즘은 문자열을 정수로 바꾸어주기 때문에 문자열 비교에서 정수의 이점을 이용할 수 있다.

• 정수의 비교 O(1)
• 배열을 이용할 수 있음. ex) arr[Hash("string")] = 1

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

 

3. 라빈 카프 알고리즘 구현

int match(string s, string p) {
	int n = s.size(), m = p.size();
    int hash_p = hash(p);			//P 해쉬값, 1번호출
    for(int i=0; i<n-m; ++i) {		
    	int hash_s = hash(s.substr(i, i+m); //si의 시작위치에서 m개의 부분문자열 해쉬값, N번 호출
        if(hash_p == hash_s) {
        	if(s.substr(i, i+m) == p)
            	return i;
        }
    }
  	return -1;
}

위 경우 Hash의 시간복잡도가 O(M)이라고 한다면, 시간복잡도는 O(NM)이다.

라빈 카프의 수행 시간은 해쉬 함수에 영향을 받기 때문에,

라빈 카프에서 사용하는 해쉬 함수는 라빈 핑거프린트(rolling hash function)이다.

 

라빈 핑거프린트는 문자열을 구성하는 문자의 집합을 알고 있을 때 사용한다.

s[i]의 시작 위치에서 m개의 부분문자열의 해쉬값과 s[i+1]의 시작 위치에서 m개의 부분문자열의 해쉬값의 차이는 s[i], s[i+m]만 차이가 있다는 점을 이용해서 

이전 해쉬값을 사용해서 다음 해쉬값을 구하는 방법으로 시간복잡도를 O(1)로 줄일 수 있다.

 

int mod = 127;
int base = 256;

int rabin_hash(string s) {
	int ans = 0;
	for (char ch : s) {
		ans = (ans * base + ch) % mod;
	}
	return ans;
}
int rabin_karp(string &s, string &p) {
	int n = s.length(), m = p.length();
	if (n < m) return -1;	// 패턴이 문자열보다 길면 찾을 수 없음.
	int hash_p = rabin_hash(p), hash_s = rabin_hash(s.substr(0, m));
	int first = 1;

	for (int i = 0; i<m - 1; i++) 
		first = (first * base) % mod;

	for (int i = 0; i <= n - m; i++) {
		if (hash_p == hash_s) 
			if (s.substr(i, m) == p) return i;		// 패턴의 시작위치 리턴
		
		if (i + m < n) {
			hash_s = hash_s - (s[i] * first) % mod;
			hash_s = (hash_s + mod) % mod;	// 음수 값을 가질 수도 있으므로
			hash_s = ((hash_s * base) % mod + s[i + m]) % mod;
		}
	}
	return -1;	// 찾은 문자열이 없다면 리턴 -1
}

 

해쉬값이 일치하면 문자열이 같다고 판단할 수 있지만, 실제 해쉬함수는 해쉬 충돌(hash nollison)로 다른 문자열이 공통된 해쉬값을 갖는 게 가능하기 때문에, 해쉬값이 같을 경우 일대일 매칭으로 일치하는지 확인하는 과정을 가져야 된다. 

 

시간복잡도 

• 보통 : 해쉬의 시간복잡도가 O(M)이라고 한다면
• 최악의 경우 : 해쉬함수가 좋지 않아서 각각 다른 문자열이 공통된 해쉬값을 가질 경우 O(NM)

 

좋은 해쉬를 가지는 방법은 많은 방법이 있지만..!
라빈 핑거프린트 해쉬알고리즘을 사용할 경우 다음 해쉬값을 편하게 구할 수 있다.

 

정답은 없다. 이것저것 해보면서 문제마다 가장 좋은 진법과 소수를 구해야 된다.

즉, 소수를 매우 큰 값(ex 2147483647)으로 만들고 실제 문자열과 비교 없이 풀어도 된다.

 

만약, 패턴의 문자열이 매우 길다면, 오버플로우(overflow)가 발생하게 되지만, 일반적으로 오버플로우가 발생해도 해쉬값은 동일하다고 생각해도 된다.

정확한 해쉬값의 일치 여부를 검증하기 위해 모듈러 연산을 사용하기도 한다.

 

 

4. 라빈 카프 문제 풀이

16916 부분 문자열 : https://www.acmicpc.net/problem/16916

#include <iostream>
#include <string>
using namespace std;
int mod = 127;
int base = 256;

int rabin_hash(string s) {
	int ans = 0;
	for (char ch : s) {
		ans = (ans * base + ch) % mod;
	}
	return ans;
}
int rabin_karp(string &s, string &p) {
	int n = s.length(), m = p.length();
	if (n < m) return 0;	
	int hash_p = rabin_hash(p), hash_s = rabin_hash(s.substr(0, m));
	int first = 1;

	for (int i = 0; i<m - 1; i++) 
		first = (first * base) % mod;

	for (int i = 0; i <= n - m; i++) {
		if (hash_p == hash_s) 
			if (s.substr(i, m) == p) return 1;		
		
		if (i + m < n) {
			hash_s = hash_s - (s[i] * first) % mod;
			hash_s = (hash_s + mod) % mod;
			hash_s = ((hash_s * base) % mod + s[i + m]) % mod;
		}
	}
	return 0;	
}
int main() {
	string s, p;
	cin >> s >> p;
	cout << rabin_karp(s, p) << '\n';
	return 0;
}