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
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";
}
}
Space Complexity: O(n)2
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)

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)2
Space Complexity: O(n)
References


