The longest common substring (LCS) of two input strings s,t is a common substrin
ID: 651980 • Letter: T
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 O(nlgn) 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?
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.