Longest Repeating Substring
To solve the problem of finding the length of the longest repeating substring, we can use the binary search algorithm combined with the RabinKarp algorithm for string matching.
Here’s how the solution works:
Binary Search for Length: Perform a binary search on the length of the substring we want to find (from 1 to the length of the string). For each candidate length
L
, we will use a rolling hash to check if there’s a repeating substring with lengthL
.RabinKarp Algorithm for String Matching: The RabinKarp algorithm uses hashing to find substring matches. We will use it to find if there are repeating substrings with a given length
L
.Update Solution: If we find a repeating substring with length
L
, we will update our binary search range to look for longer substrings. If not, we will look for shorter substrings.
Here’s the code:


Key Takeaways
 Binary Search: Using binary search to look for the optimal length helps reduce the time complexity.
 RabinKarp Algorithm: The RabinKarp algorithm is an efficient way to look for substring matches.
 Time Complexity: The overall time complexity of this solution is O(N * log N), where N is the length of the string.
 Space Complexity: The space complexity is O(N), as we are storing the hashes of substrings.