title: Fast implementation of Rolling hash
body: <p>I need a Rolling hash to search for patterns in a file. (I am trying to use the <a href="https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm" rel="nofollow noreferrer">Rabin-Karp string search algorithm</a>).</p>
  
  <p>I understand how a good <strong>Hash</strong> works and how a good <strong>Rolling Hash</strong> should work but I am unable to figure out how to efficiently implement the <em>divide</em> (or inverse multiplication) when rolling the hash. I also read rsync uses rolling version of <em>adler32</em> but that doesn't looks like a random enough hash.</p>
  
  <p>Ideally it will be great if you can point me to an optimized C/C++ implementation, but any pointers in the right direction will help.</p>