def fingerprint(string,basis=2**16,r=2**32-3):
    """ used to computes karp-rabin fingerprint of the pattern
    employs Horner method (modulo r) """
    partial_sum=0
    for x in string:
        partial_sum=(partial_sum*basis+ord(x)) % r
    return partial_sum

def text_fingerprint(string,length,basis=2**16,r=2**32-3):
    """ used to computes karp-rabin fingerprint of the text """
    f=[]
    b_power=pow(basis,length-1,r)
    list.append(f, fingerprint(string[0:length],basis,r))
    # f[0] equals first text fingerprint 
    for s in range(1,len(string)-length+1):
        new_fingerprint=((f[s-1]-ord(string[s-1])*b_power)*basis
                         +ord(string[s+length-1])) % r
            # compute f[s], based on f[s-1]
        list.append(f,new_fingerprint)# append f[s] to existing f       
    return f


def find_matches_KR(pattern,text,basis=2**16,r=2**32-3):
    if len(pattern) > len(text):
        return []
    p=fingerprint(pattern,basis,r)
    f=text_fingerprint(text,len(pattern),basis,r)
    matches = [s for s, f_s in enumerate(f) if f_s == p]
    # list comprehension 
    return matches

def find_matches_KR_safe(pattern,text,basis=2**16,r=2**32-3):
	""" safe version of KR
		checks every suspect for a match"""
	if len(pattern) > len(text):
		return []
	p=fingerprint(pattern,basis,r)
	f=text_fingerprint(text,len(pattern),basis,r)
	matches = [s for s, f_s in enumerate(f) if f_s == p\
    	and text[s:s+len(pattern)]==pattern]
	# list comprehension 
	return matches