Introduction

Given a string str, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. If there exists more than one such substring return any of them.

Input : str = "banana"
Output : an 
         or na

Input : str = "geeksforgeeks"
Output : geeks

Sample Examples

Approach

There are two approaches for the given problem. We can take the DP approach or the LPS (Longest possible suffix which is also a prefix and preprocessing of KMP algorithm).

DP based

The idea is look for each letter repeating in the string and update the DP array.

In the below example we go letter by lettter and compares with the next letters,

If a match is found we add 1 and previous element repeat count
Previous element is diagonally up left, which is 0 for the first row
If a match is not found we set it to 0

Note: A condition is added to make sure the range is not overlapping by using the j-1 and previous dp count.

using System;
public class GFG {
    public static void Main()
    {
        var t = int.Parse(Console.ReadLine() ?? "0");
        while (t-- > 0)
        {
            var n = int.Parse(Console.ReadLine() ?? "0");
            var str = Console.ReadLine();
            Console.WriteLine(MaxRepeatNonOverlapSubstrDp(str, n));
        }
    }

    private static string MaxRepeatNonOverlapSubstrDp(string str, int n)
    {
        if (string.IsNullOrEmpty(str))
        {
            return str;
        }

        var dp = new int[n + 1, n + 1];
        // dp [i,j] denotes the length of substring at i, j which is repeating 
        // and non overlapping

        var index = 0;
        var max = 0;

        for (var i = 1; i <= n; i++)
        {
            for (var j = i + 1; j <= n; j++)
            {
                // essential condition to see if the elements repeats
                if (str[j - 1] == str[i - 1]
                    && j - i > dp[i - 1, j - 1])
                    // verify that the range is greater than the previous
                    // count of the substring to ensure non overlap
                {
                    dp[i, j] = 1 + dp[i - 1, j - 1];
                    if (dp[i, j] > max)
                    {
                        max = dp[i, j];
                        index = i - max;
                    }
                }
            }
        }

        return max > 0 ? str.Substring(index, max) : "-1";
    }
}

Program using the DP based approach

Time Complexity: O(n)²
Space Complexity: O(n)²

LPS based (KMP Preprocessing)

This approach is based on the preprocessing for the KMP using the LPS (longest possible suffix which is also a prefix)

Modified LPS with range for non-overlapping

Below implementation uses the start variable to use instead of 0 in case of normal LPS implementations.

using System;
public class GFG {
    public static void Main()
    {
        var t = int.Parse(Console.ReadLine() ?? "0");
        while (t-- > 0)
        {
            var n = int.Parse(Console.ReadLine() ?? "0");
            var str = Console.ReadLine();
            Console.WriteLine(MaxRepeatNonOverlapSubstrLps(str, n));
        }
    }
    
    private static string MaxRepeatNonOverlapSubstrLps(string str, int n)
    {
        if (string.IsNullOrEmpty(str))
        {
            return str;
        }

        var index = 0;
        var max = 0;

        var lps = new int[n];
        for (var start = 0; start < n; start++)
        {
            var i = start;
            for (var j = i + 1; j < n; )
            {
                if (str[i] == str[j])
                {
                    // Added for non overlapping
                    if (j - i > i - start)
                    {
                        lps[j] = i - start + 1;
                        if (lps[j] > max)
                        {
                            max = lps[j];
                            index = start;
                        }

                        i++;
                        j++;
                    }
                    else
                    {
                        i = lps[i];
                    }
                }
                else if (i != start) // start is used instead of 0
                {
                    i = lps[i - 1];
                    if (i < start) // set the start
                    {
                        i = start;
                    }
                }
                else
                {
                    lps[j] = 0;
                    j++;
                }
            }
            Array.Clear(lps, 0, lps.Length);
        }

        return max > 0 ? str.Substring(index, max) : "-1";
    }
}

Time Complexity: O(n)²
Space Complexity: O(n)