Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- My attempt at variable length rolling hash https://www.youtube.com/watch?v=w6nuXg0BISo
- """
- class VariableLengthRollingHash():
- def __init__(self, base=257, prime=1000000007):
- self.base = base
- self.prime = prime
- self.base_inverse = pow(base, prime-2, prime)
- self.max_base = self.base_inverse
- self.u_mod_p = 0
- def hash(self):
- return self.u_mod_p
- def append(self, val):
- if len(val) > 1:
- for v in val:
- self.append(v)
- return
- self.u_mod_p = (self.u_mod_p * self.base + ord(val)) % self.prime
- self.max_base = (self.max_base * self.base) % self.prime
- # print('a %s --------- %s' % (self.u_mod_p, self.max_base))
- def skip(self, val):
- if len(val) > 1:
- for v in val:
- self.skip(v)
- return
- self.u_mod_p = (self.u_mod_p - ord(val) * self.max_base) % self.prime
- self.max_base = (self.max_base * self.base_inverse) % self.prime
- # print('s %s --------- %s' % (self.u_mod_p, self.max_base))
- def reset(self):
- self.u_mod_p = 0
- self.max_base = self.base_inverse
- def test(str1, str2):
- r1 = VariableLengthRollingHash()
- r2 = VariableLengthRollingHash()
- for l1, l2 in zip(str1, str2):
- r1.append(l1)
- r2.append(l2)
- return r1.hash() == r2.hash()
- if __name__ == '__main__':
- assert not test('apple', 'applz')
- assert test('apple', 'apple')
- b = VariableLengthRollingHash()
- b.append('hello')
- n = VariableLengthRollingHash()
- n.append('zhell')
- assert not b.hash() == n.hash()
- n.skip('z')
- assert not b.hash() == n.hash()
- n.append('o')
- assert b.hash() == n.hash()
- print('Test success')
Advertisement
Add Comment
Please, Sign In to add comment