Find longest common substring using a rolling hash

Question

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring of length $k$. We can then use binary search to find the maximum $k$. This takes time $\cal O(n \lg n)$ provided that solving the relaxed problem takes linear time.

Finding a $k$-common substring can be solved using a rolling hash:

1. Compute hash values of all $k$-length substrings of $s$ and $t$.
2. If a hash of $s$ coincides with a hash of $t,ドル then we've found a $k$-length common substring.

Step 1 uses a rolling hash to achieve linear time but I can't see how we can perform step 2. in linear time. Any suggestions?

• Yuval Filmus: Use a hash table. (Of sorts. You've already computed the hashes.)
• mrk: I still can't see how. Could you please write an answer?

Answer 1

In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t,ドル look it up on the table. This takes expected linear time for a large enough hash table.