I have made some improvement to Rabin Karp algorithm when the source and pattern only contain the characters from A to Z. The improvement is, I use base 26 for hashing (as there are total 26 characters). In this case, when the hashes match, there is no need to compare the actual string contents (since there are no hash collisions).
Below is my code in Python 2.7, any advice on code efficiency improvement (in terms of algorithm complexity perspective), bugs or code style is appreciated.
Source code in Python 2.7,
def rabin_karp_match(source, pattern): base = 26 p_hash = 0 s_hash = 0 for i in pattern: p_hash = p_hash * base + ord(i)-ord('A') for j,v in enumerate(source): if j < len(pattern) - 1: s_hash = s_hash * base + ord(v)-ord('A') continue s_hash = s_hash * base + ord(v)-ord('A') if s_hash == p_hash: return j - len(pattern)+1 s_hash = s_hash - (ord(source[j-len(pattern)+1]) - ord('A')) * base ** (len(pattern) - 1) return -1 if __name__ == "__main__": print rabin_karp_match('GACGCCA','CGC') print rabin_karp_match('GATACCCATCGAGTCGGATCGAGT', 'GAG') print rabin_karp_match('FOOBARWIDGET', 'WIDGETS')