Тэмдэгт мөр тааруулах Рабин-Карпын алгоритм¶
Энэ алгоритм нь хэшлэх ойлголт дээр суурилдаг тул хэрэв та тэмдэгт мөрийн хэшлэлттэй танил биш бол тэмдэгт мөрийн хэшлэлт өгүүллийг үз.
Энэ алгоритмыг Рабин, Карп нар 1987 онд зохиосон.
Бодлого: Хоёр тэмдэгт мөр өгөгдсөн — хэв маяг $s$ ба текст $t$, хэв маяг текстэд гарч байгаа эсэхийг тодорхойлж, хэрэв гарч байвал түүний бүх орцыг $O(|s| + |t|)$ хугацаанд тоочих.
Алгоритм: $s$ хэв маягийн хэшийг тооцоол. $t$ текстийн бүх угтварын хэш утгыг тооцоол. Одоо бид тооцоолсон хэшүүдээ ашиглан $|s|$ урттай дэд мөрийг $s$-тэй тогтмол хугацаанд харьцуулж чадна. Тиймээс $|s|$ урттай дэд мөр бүрийг хэв маягтай харьцуул. Энэ нь нийтдээ $O(|t|)$ хугацаа авна. Эндээс алгоритмын эцсийн complexity нь $O(|t| + |s|)$ болно: хэв маягийн хэшийг тооцоолоход $O(|s|)$, $|s|$ урттай дэд мөр бүрийг хэв маягтай харьцуулахад $O(|t|)$ шаардагдана.
Implementation¶
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;
}