문자열 매칭을 위한 Rabin-Karp 알고리즘¶
이 알고리즘은 해싱 개념에 기반하므로, 문자열 해싱에 익숙하지 않다면 문자열 해싱 문서를 참고하십시오.
이 알고리즘은 1987년에 Rabin과 Karp가 고안했습니다.
문제: 패턴 $s$와 텍스트 $t$라는 두 문자열이 주어질 때, 패턴이 텍스트에 나타나는지 판별하고, 나타난다면 모든 등장 위치를 $O(|s| + |t|)$ 시간에 열거하십시오.
알고리즘: 패턴 $s$의 해시를 계산합니다. 텍스트 $t$의 모든 접두사에 대한 해시 값을 계산합니다. 이제 계산한 해시를 이용하면 길이가 $|s|$인 부분 문자열을 $s$와 상수 시간에 비교할 수 있습니다. 따라서 길이가 $|s|$인 각 부분 문자열을 패턴과 비교합니다. 이 과정에는 총 $O(|t|)$ 시간이 걸립니다. 따라서 알고리즘의 최종 복잡도는 $O(|t| + |s|)$입니다. 패턴의 해시를 계산하는 데 $O(|s|)$가 필요하고, 길이가 $|s|$인 각 부분 문자열을 패턴과 비교하는 데 $O(|t|)$가 필요합니다.
구현¶
vector<int> rabin_karp(string const& s, string const& t) {
const int p = 31;
const int m = 1e9 + 9;
int S = s.size(), T = t.size();
vector<long long> p_pow(max(S, T));
p_pow[0] = 1;
for (int i = 1; i < (int)p_pow.size(); i++)
p_pow[i] = (p_pow[i-1] * p) % m;
vector<long long> h(T + 1, 0);
for (int i = 0; i < T; i++)
h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;
long long h_s = 0;
for (int i = 0; i < S; i++)
h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
vector<int> occurrences;
for (int i = 0; i + S - 1 < T; i++) {
long long cur_h = (h[i+S] + m - h[i]) % m;
if (cur_h == h_s * p_pow[i] % m)
occurrences.push_back(i);
}
return occurrences;
}