title: Why is this Rabin-Karp Code, in Python, so slow?
body: <pre><code>from time import process_time_ns
  def initial_hash(desired):
      u=0
      for i in desired:
          u=(u*256+ord(i))%89
      return u
  def find(Document):
      initial=Document[:len(desired)]
      hash_1=initial_hash(initial)
      for i in range(1,len(Document)-len(desired)+1):
          hash_1=skip(Document[i-1],hash_1)
          hash_1=append(Document[len(desired)+i-1],hash_1)
  def append(char,u):
      u=(u*256+ord(char))%89
      return u
  def skip(char,u):
      u=(u-(ord(char)*(constante)))%89
      return u
  to=process_time_ns()
  desired=&quot;ababa&quot;
  constante=(256**(len(desired)-1))%89
  hash_desired=initial_hash(desired)
  text=open(&quot;match.txt&quot;,&quot;r&quot;)
  for x in text:
      find(x)
  print(process_time_ns()-to)
  </code></pre>
  <p>I have implemented this code by following the MIT course 6006. I used in the code above some markers to see the time. I changed the <code>match.txt</code>to a lot of different sizes as well as the <code>desirable</code> variable, the one I want to find in the document. But for a lot of variations the naive algorithm described in the link is always faster. I choose 89 as prime. The code is based on this link:</p>
  <p><a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec09_orig.pdf" rel="nofollow noreferrer">https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec09_orig.pdf</a></p>