LC: Longest Repeating Substring - spiralgo/algorithms GitHub Wiki

Longest Repeating Substring

The Essence:

The general idea is that, if there is a repeating substring of length k, there might possibly be repeating substring longer than k. The information from a shorter repeating substring can be used to check for a longer substring.

Details:

There are two general approaches, both utilizing the intuition above:

1. Dynamic Programming:

Let there be a repeating substring rs, whose running length at indices i and j is h. If i+1 and j+1 have the same character, the length here would be h+1, otherwise 0. For implementing this, two loops through the string-indices and a 2D grid is enough. It can also be implemented using linear space.

2. Binary Searching:

The repeating substring length is some value between 0 and the string length. Then binary search can be used. If there is a repeating substring of length mid, then there can be a longer one. Otherwise, it must be shorter. For checking the presence of substrings of length mid, hashing is required. This can be done using non-rolling hashing as well as with rolling hashing (Rabin-Karp Algorithm).

3. Suffix Tree:

This approach is slightly independent from the general intuition. Unlike the previous 2, a suffix tree can find the longest repeating substring in linear time. However, implementing this efficiently is not trivial and requires deeper understanding at this stage. After learning about suffix trees, for more clear information, the problem-solver can check this excellent community explanation: https://stackoverflow.com/a/9513423.