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:
- Compute hash values of all $k$-length substrings of $s$ and $t$.
- 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?