title: Python: Rabin-Karp algorithm hashing
body: <p>I am implementing Rabin-Karp algorithm for fun. I came across this pseudocode:</p>
  
  <pre><code>    RABIN -KARP -MATCHER (T, P, d, q)
      1 n = T.length
      2 m = P.length
      3 h = d^(m-1) mod q
      4 p=0
      5 t= 0
      6 for i = 1 to m
      / preprocessing
      /
      7 p = (dp + P [i]) mod q
      8 t = (dt + T [i]) mod q
      9 for s = 0 to n-m
      / matching
      /
      10     if p == t
      11         if P [1... m] == T [s + 1...s + m]
      12             print “Pattern occurs with shift” s
      13     if s &lt; n-m
      14         t  = (d(t-T[s + 1]h) + T [s + m + 1]) mod q
  </code></pre>
  
  <p>I implemented in Python 2.7 like so:</p>
  
  <pre><code>def Rabin_Karp_Matcher(text, pattern, d, q):
      n = len(text)
      m = len(pattern)
      h = pow(d,m-1)%q
      p = 0
      t =0
      result = []
      for i in range(m): # preprocessing
          p = (d*p+ord(pattern[i]))%q
          t = (d*t+ord(text[i]))%q
      for s in range(n-m):
          if p == t: # check character by character
              match = True
              for i in range(m):
                  if pattern[i] != text[s+i]:
                      match = False
                      break
              if match:
                  result = result + [s]
          if s &lt; n-m:
                  t = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here
      return result
  </code></pre>
  
  <p>where result is a list containing the index in text of pattern.</p>
  
  <p>My code is failing to find the 26 in 3141592653589793
   and I suspect it has something to do with my hashcode defined by line 14 of the pseudocode. Can anyone please help with this.</p>
  
  <p>I passed in the following paramters:</p>
  
  <p>P = "26"
  T = "3141592653589793"
  d = 257
  q = 11</p>
  
  <p>P and T must be strings/arrays of chars</p>