rabin-karp algorithm
1 function RabinKarp(string s[1..n], string pattern[1..m])
2 hpattern := hash(pattern[1..m]);
3 for i from 1 to n-m+1
4 hs := hash(s[i..i+m-1])
5 if hs = hpattern
6 if s[i..i+m-1] = pattern[1..m]
7 return i
8 return not foundrabin karp cp algorithm
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> occurences;
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)
occurences.push_back(i);
}
return occurences;
}rabin karp algorithm
class Encoder:
def __init__(self, string, to_show, warning: int = None, mod_value=11):
self.control = warning if warning is not None else to_show
self.range = [0, to_show]
self.hashed = 0
self.container = []
"""to avoid large value not needed in python (but consumes large space if ignored)"""
self.mod_value = mod_value
self.encode_them(string)
def encode_them(self, string):
self.container = [ord(_) for _ in string]
length = self.range[1] - self.range[0]
for i in range(length):
self.hashed += self.container[i] * (10 ** ((length - i - 1) % self.mod_value))
def shift(self):
if self.range[1] >= self.control:
return ""
length = self.range[1] - self.range[0]
self.hashed -= self.container[self.range[0]] * (10 ** ((length - 1) % self.mod_value))
self.hashed *= 10
self.hashed += self.container[self.range[1]]
self.range[0], self.range[1] = self.range[0] + 1, self.range[1] + 1
def rabin_karp_match(main_string, sub_string, mod_value=11):
main_length, sub_length = len(main_string), len(sub_string)
if sub_string == 0:
return 0
if sub_length > main_length:return -1
main, sub = Encoder(main_string, sub_length, main_length, mod_value), Encoder(sub_string, sub_length, warning=None,
mod_value=mod_value)
matches = [0]
for i in range(main_length - sub_length + 1):
if main.hashed == sub.hashed:
if main_string[i: i + sub_length] == sub_string:
matches[0] += 1
matches.append(i)
main.shift()
return tuple(matches)
print(rabin_karp_match("Rem-Rem", "Rem", 2))
print(rabin_karp_match("AYA-AYA", "AYA"))
print(rabin_karp_match("JOJO", "JO"))
print(rabin_karp_match("aaaa", "b"))
print(rabin_karp_match("sd",""))Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
