rabin karp algorithm code example

Example 1: 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 found

Example 2: rabin 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;
}

Example 3: 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",""))