String Submatching with rolling hash

rollhash.py

# Rolling hash
# Rabin-Karp Algorithm
needle = "you"
haystack = "hello, how are you doing this fine day?"
s = map(ord, haystack)
BASE = max(s) + 1
BIG_PRIME = 472882027 # 15485863
needle_length = len(needle)
# large prime
"""
Hash Function using global BASE, needle_length, and big prime
"""
def h(s, start=0):
	return sum([s[start+i]* (BASE**(needle_length-i-1)) for i in range(needle_length)]) % BIG_PRIME
'''
Returns the hash value for the next value of i, given the current hash and index
Uses same globals
'''
def next_h(cur_h, s, i):
	return (BASE * (cur_h - (BASE**(needle_length-1)) *s[i]) + s[i+needle_length]) % BIG_PRIME

inital_hash = h(s)
needle_hash = h(map(ord,needle))
next_hash = inital_hash

for i in range(len(haystack)-needle_length):
	next_hash = next_h(next_hash, s, i)
	if next_hash == needle_hash:
		print "found at position", i+1 
		break
else:
	print "not found"