title: longest common substring with a rolling hash
body: <p>I'm implementing the <strong>longest common substring</strong> problem with a rolling hash logic and I can't understand how it works in <code>O(nlogn)</code> time. The algorithm states that,</p>
  
  <pre><code>1) choose a length of substring by binary search( low, high, mid)
  2) Compute rolling hash values for both strings for a given length mid
  3) match the two rolling hashes and see if they are the same and reposition the binary search accordingly.
  </code></pre>
  
  <p>I can see that computing the rolling hashes is O(n) and the binary search for length is O(logn) thus giving O(nlogn), but from what I understand, the rolling hashes by themselves are not sufficient to get a guaranteed hit. Multiple substrings could have the same rolling hash value, so its another times O(n) to check if the strings really match. Am I missing something?</p>