Guest User

variable length rolling hash python

a guest
Oct 11th, 2017
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.79 KB | None | 0 0
  1. """
  2. My attempt at variable length rolling hash https://www.youtube.com/watch?v=w6nuXg0BISo
  3. """
  4.  
  5. class VariableLengthRollingHash():
  6.  
  7.     def __init__(self, base=257, prime=1000000007):
  8.         self.base = base
  9.         self.prime = prime
  10.         self.base_inverse = pow(base, prime-2, prime)
  11.         self.max_base = self.base_inverse
  12.         self.u_mod_p = 0
  13.  
  14.     def hash(self):
  15.         return self.u_mod_p
  16.  
  17.     def append(self, val):
  18.         if len(val) > 1:
  19.             for v in val:
  20.                 self.append(v)
  21.             return
  22.         self.u_mod_p = (self.u_mod_p * self.base + ord(val)) % self.prime
  23.         self.max_base = (self.max_base * self.base) % self.prime
  24.         # print('a %s  --------- %s' % (self.u_mod_p, self.max_base))
  25.  
  26.     def skip(self, val):
  27.         if len(val) > 1:
  28.             for v in val:
  29.                 self.skip(v)
  30.             return
  31.         self.u_mod_p = (self.u_mod_p - ord(val) * self.max_base) % self.prime
  32.         self.max_base = (self.max_base * self.base_inverse) % self.prime
  33.         # print('s %s  --------- %s' % (self.u_mod_p, self.max_base))
  34.  
  35.     def reset(self):
  36.         self.u_mod_p = 0
  37.         self.max_base = self.base_inverse
  38.  
  39.  
  40. def test(str1, str2):
  41.     r1 = VariableLengthRollingHash()
  42.     r2 = VariableLengthRollingHash()
  43.  
  44.     for l1, l2 in zip(str1, str2):
  45.         r1.append(l1)
  46.         r2.append(l2)
  47.  
  48.     return r1.hash() == r2.hash()
  49.  
  50. if __name__ == '__main__':
  51.     assert not test('apple', 'applz')
  52.     assert test('apple', 'apple')
  53.  
  54.     b = VariableLengthRollingHash()
  55.     b.append('hello')
  56.     n = VariableLengthRollingHash()
  57.     n.append('zhell')
  58.  
  59.     assert not b.hash() == n.hash()
  60.     n.skip('z')
  61.     assert not b.hash() == n.hash()
  62.     n.append('o')
  63.     assert b.hash() == n.hash()
  64.     print('Test success')
Advertisement
Add Comment
Please, Sign In to add comment