-
Notifications
You must be signed in to change notification settings - Fork 2
/
Rabin-Karp.cpp
45 lines (38 loc) · 1.23 KB
/
Rabin-Karp.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
size_t rabin_karp(const string &s,
const string &p) {
if (s.size() < p.size()) return 0;
auto n = s.size(), m = p.size();
const ll p1 = 31, p2 = 29, q1 = 1e9 + 7,
q2 = 1e9 + 9;
const ll p1_1 = fpow(p1, q1 - 2, q1),
p1_2 = fpow(p1, m - 1, q1);
const ll p2_1 = fpow(p2, q2 - 2, q2),
p2_2 = fpow(p2, m - 1, q2);
pair<ll, ll> hs, hp;
for (int i = (int)m - 1; ~i; --i) {
hs.first = (hs.first * p1) % q1;
hs.first = (hs.first + (s[i] - 'a' + 1)) % q1;
hs.second = (hs.second * p2) % q2;
hs.second =
(hs.second + (s[i] - 'a' + 1)) % q2;
hp.first = (hp.first * p1) % q1;
hp.first = (hp.first + (p[i] - 'a' + 1)) % q1;
hp.second = (hp.second * p2) % q2;
hp.second =
(hp.second + (p[i] - 'a' + 1)) % q2;
}
size_t occ = 0;
for (size_t i = 0; i < n - m; i++) {
occ += (hs == hp);
int fi = s[i] - 'a' + 1;
int fm = s[i + m] - 'a' + 1;
hs.first = (hs.first - fi + q1) % q1;
hs.first = (hs.first * p1_1) % q1;
hs.first = (hs.first + fm * p1_2) % q1;
hs.second = (hs.second - fi + q2) % q2;
hs.second = (hs.second * p2_1) % q2;
hs.second = (hs.second + fm * p2_2) % q2;
}
occ += hs == hp;
return occ;
}