Substring repetida y no superpuesta más larga

Dada una string str , busque la substring repetida más larga que no se superponga. En otras palabras, encuentre 2 substrings idénticas de longitud máxima que no se superpongan. Si existe más de una de esas substrings, devuelva cualquiera de ellas.

Ejemplos: 

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

Solución ingenua : el problema se puede resolver fácilmente tomando todas las substrings posibles y, para todas las substrings, verifique la string restante (no superpuesta) si existe una substring idéntica. Hay O(n ² ) substrings en total y compararlas con la string restante llevará O(n) tiempo. Entonces, la complejidad temporal total de la solución anterior es O(n ³ ). 

Programación Dinámica : Este problema se puede resolver en tiempo O(n ² ) usando Programación Dinámica. La idea básica es encontrar el sufijo repetido más largo para todos los prefijos en la 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

Para evitar la superposición, debemos asegurarnos de que la longitud del sufijo sea menor que (ji) en cualquier instante. 
El valor máximo de LCSRe(i, j) proporciona la longitud de la substring repetida más larga y la substring misma se puede encontrar utilizando la longitud y el índice final del sufijo común.

A continuación se muestra la implementación de la recurrencia. 

// C++ program to find the longest repeated
// non-overlapping substring
#include<bits/stdc++.h>
using namespace std;
 
// Returns the longest repeating non-overlapping
// substring in str
string longestRepeatedSubstring(string str)
{
    int n = str.length();
    int LCSRe[n+1][n+1];
 
    // Setting all to 0
    memset(LCSRe, 0, sizeof(LCSRe));
 
    string res; // To store result
    int res_length  = 0; // To store length of result
 
    // building table in bottom-up manner
    int i, index = 0;
    for (i=1; i<=n; i++)
    {
        for (int j=i+1; j<=n; j++)
        {
            // (j-i) > LCSRe[i-1][j-1] to remove
            // overlapping
            if (str[i-1] == str[j-1] &&
                LCSRe[i-1][j-1] < (j - i))
            {
                LCSRe[i][j] = LCSRe[i-1][j-1] + 1;
 
                // updating maximum length of the
                // substring and updating the finishing
                // index of the suffix
                if (LCSRe[i][j] > res_length)
                {
                    res_length = LCSRe[i][j];
                    index = max(i, index);
                }
            }
            else
                LCSRe[i][j] = 0;
        }
    }
 
    // If we have non-empty result, then insert all
    // characters from first character to last
    // character of string
    if (res_length > 0)
        for (i = index - res_length + 1; i <= index; i++)
            res.push_back(str[i-1]);
 
    return res;
}
 
// Driver program to test the above function
int main()
{
    string str = "geeksforgeeks";
    cout << longestRepeatedSubstring(str);
    return 0;
}

// Java program to find the longest repeated
// non-overlapping substring
 
class GFG {
 
// Returns the longest repeating non-overlapping
// substring in str
    static String longestRepeatedSubstring(String str) {
        int n = str.length();
        int LCSRe[][] = new int[n + 1][n + 1];
 
        String res = ""; // To store result
        int res_length = 0; // To store length of result
 
        // building table in bottom-up manner
        int i, index = 0;
        for (i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                // (j-i) > LCSRe[i-1][j-1] to remove
                // overlapping
                if (str.charAt(i - 1) == str.charAt(j - 1)
                        && LCSRe[i - 1][j - 1] < (j - i)) {
                    LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1;
 
                    // updating maximum length of the
                    // substring and updating the finishing
                    // index of the suffix
                    if (LCSRe[i][j] > res_length) {
                        res_length = LCSRe[i][j];
                        index = Math.max(i, index);
                    }
                } else {
                    LCSRe[i][j] = 0;
                }
            }
        }
 
        // If we have non-empty result, then insert all
        // characters from first character to last
        // character of String
        if (res_length > 0) {
            for (i = index - res_length + 1; i <= index; i++) {
                res += str.charAt(i - 1);
            }
        }
 
        return res;
    }
 
// Driver program to test the above function
    public static void main(String[] args) {
        String str = "geeksforgeeks";
        System.out.println(longestRepeatedSubstring(str));
    }
}
// This code is contributed by Rajput-JI

# Python 3 program to find the longest repeated
# non-overlapping substring
 
# Returns the longest repeating non-overlapping
# substring in str
def longestRepeatedSubstring(str):
 
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
                for y in range(n + 1)]
 
    res = "" # To store result
    res_length = 0 # To store length of result
 
    # building table in bottom-up manner
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
             
            # (j-i) > LCSRe[i-1][j-1] to remove
            # overlapping
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
 
                # updating maximum length of the
                # substring and updating the finishing
                # index of the suffix
                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)
                 
            else:
                LCSRe[i][j] = 0
 
    # If we have non-empty result, then insert
    # all characters from first character to
    # last character of string
    if (res_length > 0):
        for i in range(index - res_length + 1,
                                    index + 1):
            res = res + str[i - 1]
 
    return res
 
# Driver Code
if __name__ == "__main__":
     
    str = "geeksforgeeks"
    print(longestRepeatedSubstring(str))
 
# This code is contributed by ita_c

// C# program to find the longest repeated
// non-overlapping substring
using System;
  
public class GFG {
  
// Returns the longest repeating non-overlapping
// substring in str
    static String longestRepeatedSubstring(String str) {
        int n = str.Length;
        int [,]LCSRe = new int[n + 1,n + 1];
  
        String res = ""; // To store result
        int res_length = 0; // To store length of result
  
        // building table in bottom-up manner
        int i, index = 0;
        for (i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                // (j-i) > LCSRe[i-1][j-1] to remove
                // overlapping
                if (str[i - 1] == str[j - 1]
                        && LCSRe[i - 1,j - 1] < (j - i)) {
                    LCSRe[i,j] = LCSRe[i - 1,j - 1] + 1;
  
                    // updating maximum length of the
                    // substring and updating the finishing
                    // index of the suffix
                    if (LCSRe[i,j] > res_length) {
                        res_length = LCSRe[i,j];
                        index = Math.Max(i, index);
                    }
                } else {
                    LCSRe[i,j] = 0;
                }
            }
        }
  
        // If we have non-empty result, then insert all
        // characters from first character to last
        // character of String
        if (res_length > 0) {
            for (i = index - res_length + 1; i <= index; i++) {
                res += str[i - 1];
            }
        }
  
        return res;
    }
  
// Driver program to test the above function
    public static void Main() {
        String str = "geeksforgeeks";
        Console.WriteLine(longestRepeatedSubstring(str));
    }
}
// This code is contributed by Rajput-JI

<script>
// Javascript program to find the longest repeated
// non-overlapping substring
   
    // Returns the longest repeating non-overlapping
    // substring in str
    function longestRepeatedSubstring(str)
    {
        let n = str.length;
        let LCSRe = new Array(n+1);
        for(let i = 0; i < n + 1; i++)
        {
            LCSRe[i] = new Array(n+1);
        }
        for(let i = 0; i < n + 1; i++)
        {
            for(let j = 0; j < n + 1; j++)
            {
                LCSRe[i][j] = 0;
            }
        }
         
        let res = ""; // To store result
        let res_length = 0; // To store length of result
         
        // building table in bottom-up manner
        let i, index = 0;
        for (i = 1; i <= n; i++)
        {
            for (let j = i + 1; j <= n; j++)
            {
             
                // (j-i) > LCSRe[i-1][j-1] to remove
                // overlapping
                if (str[i-1] == str[j-1]
                        && LCSRe[i - 1][j - 1] < (j - i))
                {
                    LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1;
   
                    // updating maximum length of the
                    // substring and updating the finishing
                    // index of the suffix
                    if (LCSRe[i][j] > res_length)
                    {
                        res_length = LCSRe[i][j];
                        index = Math.max(i, index);
                    }
                }
                else
                {
                    LCSRe[i][j] = 0;
                }
            }
        }
   
        // If we have non-empty result, then insert all
        // characters from first character to last
        // character of String
        if (res_length > 0) {
            for (i = index - res_length + 1; i <= index; i++) {
                res += str.charAt(i - 1);
            }
        }
   
        return res;
    }
     
    // Driver program to test the above function
    let str= "geeksforgeeks";
    document.write(longestRepeatedSubstring(str));
     
    // This code is contributed by rag2127
</script>

geeks

Complejidad de Tiempo: O(n ² ) 
Espacio Auxiliar: O(n ² )

Referencias:  
https://www.geeksforgeeks.org/longest-common-substring/

Este artículo es una contribución de Ayush Khanduri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.