(1) How do I use rolling hash and binary search to find the longest common sub-string? - Quora

(1) How do I use rolling hash and binary search to find the longest common sub-string? - Quora

he main idea for using binary search in this problem is, if you have a common substring of some length 'n', then we can definitely find a common substring of length less than 'n'.


So finding the longest common substring involves the following steps:

1 2 3 4 5 6 7 8 9

hash1[] = hash of string 1 hash2[] = hash of string 2 lo = 0 hi = length of shorter string + 1 mid = (lo + hi) / 2 if (common substring of length == mid):     lo = mid else     hi = mid

Naive method for finding common substring will run in O(n^2) but you can do it in O(nlogn). Store the hashes of each substring of length 'n' of a string in a STL Set then calculate hash for each substring of length 'n' for the other string and search it in the set. So the overall complexity of this will be O(n*logn^2).

You can try this problem A Story with Strings and check some ACed solutions if you have trouble implementing.

Read full article from (1) How do I use rolling hash and binary search to find the longest common sub-string? - Quora