6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Use a hash table. (Of sorts. You've already computed the hashes.) $\endgroup$ – Yuval Filmus May 26 '14 at 23:06
  • $\begingroup$ I still can't see how. Could you please write an answer? $\endgroup$ – saadtaame May 27 '14 at 9:21
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.