Longest Repeating and Non - Overlapping Substring

In the world of string processing, finding the longest repeating and non - overlapping substring is a fascinating problem. It has applications in various fields such as data compression (where repeated patterns can be exploited for efficient encoding), bioinformatics (identifying repeated DNA sequences), and text analysis. In this blog, we will explore different approaches to solve this problem, understand common and best practices, and see example usages.

Table of Contents#

  1. Problem Definition
  2. Brute - Force Approach
    • Explanation
    • Complexity Analysis
    • Example Usage
  3. Suffix Array Approach
    • Explanation
    • Complexity Analysis
    • Example Usage
  4. Dynamic Programming Approach
    • Explanation
    • Complexity Analysis
    • Example Usage
  5. Common Practices
  6. Best Practices
  7. References

1. Problem Definition#

Given a string s, we need to find the longest substring that repeats at least twice and the occurrences of the substring do not overlap. For example, in the string s = "ababab", the longest repeating non - overlapping substring is "ab" (repeats 3 times, but the non - overlapping part is considered as two occurrences: positions 0 - 1 and 2 - 3).

2. Brute - Force Approach#

Explanation#

The brute - force approach involves checking all possible substrings. For each possible substring length l (starting from the maximum possible length down to 1), we check if there are at least two non - overlapping occurrences of a substring of length l.

Complexity Analysis#

  • Time Complexity: $O(n^3)$ where n is the length of the string. For each possible substring length l (up to n), and for each starting position i (up to n - l), and for each other starting position j (up to n - l), we check if the substrings are equal.
  • Space Complexity: $O(1)$ (assuming we are only using a few variables for comparison)

Example Usage#

def longest_repeating_non_overlapping_brute(s):
    n = len(s)
    max_len = 0
    result = ""
    for l in range(n//2, 0, -1):
        for i in range(n - l + 1):
            sub = s[i:i + l]
            for j in range(i + l, n - l + 1):
                if sub == s[j:j + l]:
                    if l > max_len:
                        max_len = l
                        result = sub
                    break
    return result
 
 
s = "ababab"
print(longest_repeating_non_overlapping_brute(s))

3. Suffix Array Approach#

Explanation#

A suffix array is an array that contains all the suffixes of a string in lexicographical order. We can use the suffix array to find the longest common prefix (LCP) between adjacent suffixes. By iterating through the LCP array, we can find the longest repeated substring. To ensure non - overlapping, we can keep track of the positions of the suffixes.

Complexity Analysis#

  • Time Complexity: $O(n\log n)$ for building the suffix array (using efficient algorithms like the induced - sorting algorithm for suffix array construction) and $O(n)$ for traversing the LCP array.
  • Space Complexity: $O(n)$ for storing the suffix array and LCP array.

Example Usage#

def build_suffix_array(s):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort()
    return [suf[1] for suf in suffixes]
 
 
def build_lcp(s, suffix_array):
    n = len(s)
    rank = [0] * n
    for i in range(n):
        rank[suffix_array[i]] = i
    lcp = [0] * n
    k = 0
    for i in range(n):
        if rank[i] == n - 1:
            k = 0
            continue
        j = suffix_array[rank[i]+1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = k
        if k > 0:
            k -= 1
    return lcp
 
 
def longest_repeating_non_overlapping_suffix(s):
    suffix_array = build_suffix_array(s)
    lcp = build_lcp(s, suffix_array)
    n = len(s)
    max_len = 0
    result = ""
    for i in range(len(lcp)):
        l = lcp[i]
        if l > 0:
            idx1 = suffix_array[i]
            idx2 = suffix_array[i + 1]
            for k in range(l, 0, -1):
                if abs(idx1 - idx2) >= k:
                    if k > max_len:
                        max_len = k
                        result = s[idx1:idx1 + k]
                    break
    return result
 
 
s = "ababab"
print(longest_repeating_non_overlapping_suffix(s))

4. Dynamic Programming Approach#

Explanation#

We can use a 2D dynamic programming table dp[i][j] which represents the length of the longest common suffix of the substrings s[0..i] and s[0..j]. We fill this table and look for the maximum value where the distance between i and j is at least the length of the common suffix (to ensure non - overlapping).

Complexity Analysis#

  • Time Complexity: $O(n^2)$ for filling the DP table (where n is the length of the string)
  • Space Complexity: $O(n^2)$ for the DP table (can be optimized to $O(n)$ using a 1D array if we only consider the previous row)

Example Usage#

def longest_repeating_non_overlapping_dp(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    max_len = 0
    result = ""
    for i in range(n):
        for j in range(i + 1, n):
            if s[i]==s[j]:
                if i == 0 or j == 0:
                    dp[i][j]=1
                else:
                    dp[i][j]=dp[i - 1][j - 1]+1
                if dp[i][j]>max_len and (j - i)>dp[i][j]:
                    max_len = dp[i][j]
                    result = s[i - max_len + 1:i + 1]
    return result
 
 
s = "ababab"
print(longest_repeating_non_overlapping_dp(s))

5. Common Practices#

  • Pre - processing: For large strings, pre - processing steps like building suffix arrays or using hashing (to quickly compare substrings) can be beneficial.
  • Iterative Improvement: Start with a brute - force approach for small strings and then optimize using more advanced algorithms as the string size grows.

6. Best Practices#

  • Choose the Right Algorithm: For very large strings (e.g., in the order of millions of characters), the suffix array approach is often the best choice due to its efficient construction and traversal.
  • Memory Management: When using dynamic programming, if possible, use a 1D array instead of a 2D array to save memory, especially for large strings.
  • Testing and Validation: Always test the algorithms with a variety of test cases, including edge cases (e.g., empty string, single - character string, string with all unique characters).

7. References#

2026-07