# Rabin-Karp algorithm implementation

This code uses the Rabin-Karp algorithm to compare two text files. It takes a few minutes when both files contain around 1000 words. How can I improve?

class RollingHash:
def __init__(self, text, sizeWord):
self.text = text
self.hash = 0
self.sizeWord = sizeWord

for i in range(0, sizeWord):
#subtract out the ASCII value of "a" to start the indexing at zero
self.hash += (ord(self.text[i]) - ord("a")+1)*(26**(sizeWord - i -1))
#start index of current window
self.window_start = 0
#end of index window
self.window_end = sizeWord

def move_window(self):
if self.window_end <= len(self.text) - 1:

self.hash -= (ord(self.text[self.window_start]) - ord("a")+1)*26**(self.sizeWord-1)
self.hash *= 26
self.hash += ord(self.text[self.window_end])- ord("a")+1
self.window_start += 1
self.window_end += 1

def window_text(self):
return self.text[self.window_start:self.window_end]

def rabin_karp(word, text):
if word == "" or text == "":
return None
if len(word) > len(text):
return None

rolling_hash = RollingHash(text, len(word))
word_hash = RollingHash(word, len(word))
word_hash.move_window()

for i in range(len(text) - len(word) + 1):
if rolling_hash.hash == word_hash.hash:
if rolling_hash.window_text() == word:
return i
rolling_hash.move_window()
return None


## migrated from stackoverflow.comMay 29 at 19:11

This question came from our site for professional and enthusiast programmers.

• It is not Rabin-Karp but longest common substring what you need, look it in geeksforgeeks.org/longest-common-substring-dp-29 And your implementation is realy messy. Look in geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching And afaik (sorry it was long time ago) Rabin-Karp is not the best for substring search, google for suffix trees. – user8426627 May 29 at 23:30
• @user8426627 My assignment required me to solve using Rabin-Karp. After using the code from geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching that you had mentioned above, the compile time reduce from 1m51sec to 44sec. Is it possible to modify the code to reduce more the compile time? – Chua May 30 at 4:35
• "This code uses the Rabin-Karp algorithm to compare two text files." No, it does not -- I suppose you use this code as part of a solution that compares files. Posting the whole program and some data for testing might be a good idea. – Janne Karila May 30 at 5:56