title: Rabin-Karp constant-time substring hash lookup
body: <p>Given a string <code>S[0..N-1]</code>, I want to be able to get the hash of any of its substrings <code>S[i..j]</code> in <code>O(1)</code> time, with <code>O(N)</code> preprocessing. Here's what I have so far (in Python):</p>
  
  <pre><code>BASE = 31
  
  word = "abcxxabc"
  N = len(word)
  
  powers = []
  prefix_hashes = []
  
  b = 1
  h = 0
  for i in range(N):
      powers.append(b)
      b *= BASE
  
      h += (ord(word[i]) - ord('a') + 1)
      h *= BASE
      prefix_hashes.append(h)
  
  def get_hash(i, j):
      if i == 0:
          return prefix_hashes[j]
      return prefix_hashes[j] - prefix_hashes[i - 1] * powers[j - i + 1]
  </code></pre>
  
  <p>It works very well... in Python, where I don't need to worry about possible integer overflow. I want to be able to perform above operations (effectively rewrite the whole algorithm), but modulo some big prime, so that I fit in 32-bit integer arithmetic. Here's what I came up with:</p>
  
  <pre><code>MOD = 10**9 + 7
  BASE = 31
  
  word = "abcxxabc"
  N = len(word)
  
  powers = []
  prefix_hashes = []
  
  b = 1
  h = 0
  for i in range(N):
      powers.append(b)
      b = (b * BASE) % MOD
  
      h += (ord(word[i]) - ord('a') + 1)
      h = (h * BASE) % MOD
      prefix_hashes.append(h)
  
  def get_hash(i, j):
      if i == 0:
          return prefix_hashes[j]
      return (prefix_hashes[j] - prefix_hashes[i - 1] * powers[j - i + 1]) % MOD
  </code></pre>
  
  <p>But the</p>
  
  <pre><code>prefix_hashes[i - 1] * powers_of_base[j - i + 1]
  </code></pre>
  
  <p>part can overflow quite easily for larger <code>MOD</code> values. How to go about it?</p>