Longest Repeating Substring

Geeks

Description:

Longest repeating and non-overlapping substring

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.

Example:

Input : str = "geeksforgeeks"
Output : geeks

Input : str = "aab"
Output : a

Input : str = "aabaabaaba"
Output : aaba

Input : str = "aaaaaaaaaaa"
Output : aaaaa

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

Idea:

Naive Solution : The problem can be solved easily by taking all the possible substrings and for all the substrings check it for the remaining(non-overlapping) string if there exists an identical substring. There are O(n2) total substrings and checking them against the remaining string will take O(n) time. So overall time complexity of above solution is O(n3).

Dynamic Programming : This problem can be solved in O(n2) time using Dynamic Programming. The basic idea is to find the longest repeating suffix for all prefixes in the string str.

Length of longest non-repeating substring can be recursively defined as below.

LCSRe(i, j) stores length of the matching and
            non-overlapping substrings ending 
            with i'th and j'th characters.

If str[i-1] == str[j-1] && (j-i) > LCSRe(i-1, j-1)
     LCSRe(i, j) = LCSRe(i-1, j-1) + 1, 
Else
     LCSRe(i, j) = 0

Where i varies from 1 to n and 
      j varies from i+1 to n

To avoid overlapping we have to ensure that the length of suffix is less than (j-i) at any instant. The maximum value of LCSRe(i, j) provides the length of the longest repeating substring and the substring itself can be found using the length and the ending index of the common suffix.

Note: 必须要 If str[i-1] == str[j-1] && (j-i) > LCSRe(i-1, j-1)；否则， if s = "aaaaaaa"会重复计算。

Code:

#include <vector>
#include <iostream>
#include <string>

using namespace std;

int LRS(string sInput){
    if(sInput.size()<2){
        return 0;
    }

    int sSize = sInput.size();
    vector<vector<int>> LRSCache(sSize+1, vector<int>(sSize+1, 0));
    int maxLen = 0;
    int leftInd=0;
    int rightInd=0;

    for(int i=0; i<sSize; i++){
        for(int j=i+1; j<sSize; j++){
            if(sInput[i] == sInput[j] && j-i>LRSCache[i][j]){
                LRSCache[i+1][j+1] = LRSCache[i][j] + 1;
                if(LRSCache[i+1][j+1]>maxLen){
                    maxLen=LRSCache[i+1][j+1];
                    rightInd = i;
                    leftInd = i - maxLen +1;
                }
            }
        }
    }

    cout<<sInput.substr(leftInd, rightInd-leftInd+1)<<' ';

    return maxLen;
}

int main(){
    string s;   

    s="geeksforgeeks";
    cout<<LRS(s)<<endl;

    s="aab";
    cout<<LRS(s)<<endl;

    s="aabaabaaba";
    cout<<LRS(s)<<endl;

    s="aaaaaaaaaaa";
    cout<<LRS(s)<<endl;
}