Subcadena repetida y no superpuesta más larga
Pruébalo en GfG Practice 
Producción
Producción
Producción
Producción
dado un cuerda f la tarea es encontrar el subcadena repetitiva no superpuesta más larga en ello. En otras palabras encontrar 2 subcadenas idénticas de longitud máxima que no se superponen. Devuelve -1 si no existe dicha cadena.
Nota: Son posibles múltiples respuestas, pero tenemos que devolver el subcadena cuyo primera ocurrencia es anterior.
Ejemplos:
Aporte: s = 'acdcdcdc'
Producción: 'acdc'
Explicación: La cadena 'acdc' es la subcadena más larga de s que se repite pero no se superpone.Aporte: s = 'geeksforgeeks'
Producción: 'geeks'
Explicación: La cadena 'geeks' es la subcadena más larga de s que se repite pero no se superpone.
Tabla de contenido
- Uso del método de fuerza bruta: tiempo O(n^3) y espacio O(n)
- Uso de DP de arriba hacia abajo (memorización): O(n^2) tiempo y O(n^2) espacio
- Uso de DP ascendente (tabulación): tiempo O(n^2) y espacio O(n^2)
- Uso de DP optimizado para el espacio: tiempo O(n^2) y espacio O(n)
Uso del método de fuerza bruta: tiempo O(n^3) y espacio O(n)
C++La idea es generar mucho posibles subcadenas y verifique si la subcadena existe en el restante cadena. Si la subcadena existe y su longitud es mayor que que responder a la subcadena y luego establecer respuesta a la subcadena actual.
// C++ program to find longest repeating // and non-overlapping substring // using recursion #include using namespace std ; string longestSubstring ( string & s ) { int n = s . length (); string ans = '' ; int len = 0 ; int i = 0 j = 0 ; while ( i < n && j < n ) { string curr = s . substr ( i j - i + 1 ); // If substring exists compare its length // with ans if ( s . find ( curr j + 1 ) != string :: npos && j - i + 1 > len ) { len = j - i + 1 ; ans = curr ; } // Otherwise increment i else i ++ ; j ++ ; } return len > 0 ? ans : '-1' ; } int main () { string s = 'geeksforgeeks' ; cout < < longestSubstring ( s ) < < endl ; return 0 ; }
Java // Java program to find longest repeating // and non-overlapping substring // using recursion class GfG { static String longestSubstring ( String s ) { int n = s . length (); String ans = '' ; int len = 0 ; int i = 0 j = 0 ; while ( i < n && j < n ) { String curr = s . substring ( i j + 1 ); // If substring exists compare its length // with ans if ( s . indexOf ( curr j + 1 ) != - 1 && j - i + 1 > len ) { len = j - i + 1 ; ans = curr ; } // Otherwise increment i else i ++ ; j ++ ; } return len > 0 ? ans : '-1' ; } public static void main ( String [] args ) { String s = 'geeksforgeeks' ; System . out . println ( longestSubstring ( s )); } }
Python # Python program to find longest repeating # and non-overlapping substring # using recursion def longestSubstring ( s ): n = len ( s ) ans = '' lenAns = 0 i j = 0 0 while i < n and j < n : curr = s [ i : j + 1 ] # If substring exists compare its length # with ans if s . find ( curr j + 1 ) != - 1 and j - i + 1 > lenAns : lenAns = j - i + 1 ans = curr # Otherwise increment i else : i += 1 j += 1 if lenAns > 0 : return ans return '-1' if __name__ == '__main__' : s = 'geeksforgeeks' print ( longestSubstring ( s ))
C# // C# program to find longest repeating // and non-overlapping substring // using recursion using System ; class GfG { static string longestSubstring ( string s ) { int n = s . Length ; string ans = '' ; int len = 0 ; int i = 0 j = 0 ; while ( i < n && j < n ) { string curr = s . Substring ( i j - i + 1 ); // If substring exists compare its length // with ans if ( s . IndexOf ( curr j + 1 ) != - 1 && j - i + 1 > len ) { len = j - i + 1 ; ans = curr ; } // Otherwise increment i else i ++ ; j ++ ; } return len > 0 ? ans : '-1' ; } static void Main ( string [] args ) { string s = 'geeksforgeeks' ; Console . WriteLine ( longestSubstring ( s )); } }
JavaScript // JavaScript program to find longest repeating // and non-overlapping substring // using recursion function longestSubstring ( s ) { const n = s . length ; let ans = '' ; let len = 0 ; let i = 0 j = 0 ; while ( i < n && j < n ) { const curr = s . substring ( i j + 1 ); // If substring exists compare its length // with ans if ( s . indexOf ( curr j + 1 ) !== - 1 && j - i + 1 > len ) { len = j - i + 1 ; ans = curr ; } // Otherwise increment i else i ++ ; j ++ ; } return len > 0 ? ans : '-1' ; } const s = 'geeksforgeeks' ; console . log ( longestSubstring ( s ));
Producción
geeks
Uso de DP de arriba hacia abajo (memorización): O(n^2) tiempo y O(n^2) espacio
El enfoque consiste en calcular la sufijo repetido más largo para todos los prefijos parejas en el cuerda f . Para índices i y j si s[yo] == s[j] entonces recursivamente calcular sufijo(i+1 j+1) y establecer sufijo(i j) como min(sufijo(i+1 j+1) + 1 j - i - 1) a evitar la superposición . Si los caracteres no coinciden establezca el sufijo (i j) = 0.
Nota:
- Para evitar superposiciones tenemos que asegurarnos de que la longitud de el sufijo es menor que (j-i) en cualquier instante.
- El valor máximo de sufijo(i j) proporciona la longitud de la subcadena repetida más larga y la subcadena en sí se puede encontrar utilizando la longitud y el índice inicial del sufijo común.
- sufijo(i j) almacena la longitud del sufijo común más largo entre índices yo y j asegurándolo no excede j - i - 1 para evitar superposiciones.
// C++ program to find longest repeating // and non-overlapping substring // using memoization #include using namespace std ; int findSuffix ( int i int j string & s vector < vector < int >> & memo ) { // base case if ( j == s . length ()) return 0 ; // return memoized value if ( memo [ i ][ j ] != -1 ) return memo [ i ][ j ]; // if characters match if ( s [ i ] == s [ j ]) { memo [ i ][ j ] = 1 + min ( findSuffix ( i + 1 j + 1 s memo ) j - i - 1 ); } else { memo [ i ][ j ] = 0 ; } return memo [ i ][ j ]; } string longestSubstring ( string s ) { int n = s . length (); vector < vector < int >> memo ( n vector < int > ( n -1 )); // find length of non-overlapping // substrings for all pairs (ij) for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { findSuffix ( i j s memo ); } } string ans = '' ; int ansLen = 0 ; // If length of suffix is greater // than ansLen update ans and ansLen for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( memo [ i ][ j ] > ansLen ) { ansLen = memo [ i ][ j ]; ans = s . substr ( i ansLen ); } } } return ansLen > 0 ? ans : '-1' ; } int main () { string s = 'geeksforgeeks' ; cout < < longestSubstring ( s ) < < endl ; return 0 ; }
Java // Java program to find longest repeating // and non-overlapping substring // using memoization import java.util.Arrays ; class GfG { static int findSuffix ( int i int j String s int [][] memo ) { // base case if ( j == s . length ()) return 0 ; // return memoized value if ( memo [ i ][ j ] != - 1 ) return memo [ i ][ j ] ; // if characters match if ( s . charAt ( i ) == s . charAt ( j )) { memo [ i ][ j ] = 1 + Math . min ( findSuffix ( i + 1 j + 1 s memo ) j - i - 1 ); } else { memo [ i ][ j ] = 0 ; } return memo [ i ][ j ] ; } static String longestSubstring ( String s ) { int n = s . length (); int [][] memo = new int [ n ][ n ] ; for ( int [] row : memo ) { Arrays . fill ( row - 1 ); } // find length of non-overlapping // substrings for all pairs (i j) for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { findSuffix ( i j s memo ); } } String ans = '' ; int ansLen = 0 ; // If length of suffix is greater // than ansLen update ans and ansLen for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( memo [ i ][ j ] > ansLen ) { ansLen = memo [ i ][ j ] ; ans = s . substring ( i i + ansLen ); } } } return ansLen > 0 ? ans : '-1' ; } public static void main ( String [] args ) { String s = 'geeksforgeeks' ; System . out . println ( longestSubstring ( s )); } }
Python # Python program to find longest repeating # and non-overlapping substring # using memoization def findSuffix ( i j s memo ): # base case if j == len ( s ): return 0 # return memoized value if memo [ i ][ j ] != - 1 : return memo [ i ][ j ] # if characters match if s [ i ] == s [ j ]: memo [ i ][ j ] = 1 + min ( findSuffix ( i + 1 j + 1 s memo ) j - i - 1 ) else : memo [ i ][ j ] = 0 return memo [ i ][ j ] def longestSubstring ( s ): n = len ( s ) memo = [[ - 1 ] * n for _ in range ( n )] # find length of non-overlapping # substrings for all pairs (i j) for i in range ( n ): for j in range ( i + 1 n ): findSuffix ( i j s memo ) ans = '' ansLen = 0 # If length of suffix is greater # than ansLen update ans and ansLen for i in range ( n ): for j in range ( i + 1 n ): if memo [ i ][ j ] > ansLen : ansLen = memo [ i ][ j ] ans = s [ i : i + ansLen ] if ansLen > 0 : return ans return '-1' if __name__ == '__main__' : s = 'geeksforgeeks' print ( longestSubstring ( s ))
C# // C# program to find longest repeating // and non-overlapping substring // using memoization using System ; class GfG { static int findSuffix ( int i int j string s int [ ] memo ) { // base case if ( j == s . Length ) return 0 ; // return memoized value if ( memo [ i j ] != - 1 ) return memo [ i j ]; // if characters match if ( s [ i ] == s [ j ]) { memo [ i j ] = 1 + Math . Min ( findSuffix ( i + 1 j + 1 s memo ) j - i - 1 ); } else { memo [ i j ] = 0 ; } return memo [ i j ]; } static string longestSubstring ( string s ) { int n = s . Length ; int [ ] memo = new int [ n n ]; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { memo [ i j ] = - 1 ; } } // find length of non-overlapping // substrings for all pairs (i j) for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { findSuffix ( i j s memo ); } } string ans = '' ; int ansLen = 0 ; // If length of suffix is greater // than ansLen update ans and ansLen for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( memo [ i j ] > ansLen ) { ansLen = memo [ i j ]; ans = s . Substring ( i ansLen ); } } } return ansLen > 0 ? ans : '-1' ; } static void Main ( string [] args ) { string s = 'geeksforgeeks' ; Console . WriteLine ( longestSubstring ( s )); } }
JavaScript // JavaScript program to find longest repeating // and non-overlapping substring // using memoization function findSuffix ( i j s memo ) { // base case if ( j === s . length ) return 0 ; // return memoized value if ( memo [ i ][ j ] !== - 1 ) return memo [ i ][ j ]; // if characters match if ( s [ i ] === s [ j ]) { memo [ i ][ j ] = 1 + Math . min ( findSuffix ( i + 1 j + 1 s memo ) j - i - 1 ); } else { memo [ i ][ j ] = 0 ; } return memo [ i ][ j ]; } function longestSubstring ( s ) { const n = s . length ; const memo = Array . from ({ length : n } () => Array ( n ). fill ( - 1 )); // find length of non-overlapping // substrings for all pairs (i j) for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { findSuffix ( i j s memo ); } } let ans = '' ; let ansLen = 0 ; // If length of suffix is greater // than ansLen update ans and ansLen for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { if ( memo [ i ][ j ] > ansLen ) { ansLen = memo [ i ][ j ]; ans = s . substring ( i i + ansLen ); } } } return ansLen > 0 ? ans : '-1' ; } const s = 'geeksforgeeks' ; console . log ( longestSubstring ( s ));
Producción
geeks
Uso de DP ascendente (tabulación): tiempo O(n^2) y espacio O(n^2)
C++La idea es crear una matriz 2D de tamaño (n+1)*(n+1) y calcular los sufijos repetidos más largos para todos los índices pares (i j) iterativamente. Partimos de la fin de la cuerda y trabaje hacia atrás para llenar la tabla. para cada (yo j) si s[yo] == s[j] fijamos sufijo[i][j] a min(sufijo[i+1][j+1]+1 j-i-1) evitar superposiciones; de lo contrario sufijo[i][j] = 0.
// C++ program to find longest repeating // and non-overlapping substring // using tabulation #include using namespace std ; string longestSubstring ( string s ) { int n = s . length (); vector < vector < int >> dp ( n + 1 vector < int > ( n + 1 0 )); string ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (ij) for ( int i = n -1 ; i >= 0 ; i -- ) { for ( int j = n -1 ; j > i ; j -- ) { // if characters match set value // and compare with ansLen. if ( s [ i ] == s [ j ]) { dp [ i ][ j ] = 1 + min ( dp [ i + 1 ][ j + 1 ] j - i -1 ); if ( dp [ i ][ j ] >= ansLen ) { ansLen = dp [ i ][ j ]; ans = s . substr ( i ansLen ); } } } } return ansLen > 0 ? ans : '-1' ; } int main () { string s = 'geeksforgeeks' ; cout < < longestSubstring ( s ) < < endl ; return 0 ; }
Java // Java program to find longest repeating // and non-overlapping substring // using tabulation class GfG { static String longestSubstring ( String s ) { int n = s . length (); int [][] dp = new int [ n + 1 ][ n + 1 ] ; String ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j > i ; j -- ) { // if characters match set value // and compare with ansLen. if ( s . charAt ( i ) == s . charAt ( j )) { dp [ i ][ j ] = 1 + Math . min ( dp [ i + 1 ][ j + 1 ] j - i - 1 ); if ( dp [ i ][ j ] >= ansLen ) { ansLen = dp [ i ][ j ] ; ans = s . substring ( i i + ansLen ); } } } } return ansLen > 0 ? ans : '-1' ; } public static void main ( String [] args ) { String s = 'geeksforgeeks' ; System . out . println ( longestSubstring ( s )); } }
Python # Python program to find longest repeating # and non-overlapping substring # using tabulation def longestSubstring ( s ): n = len ( s ) dp = [[ 0 ] * ( n + 1 ) for _ in range ( n + 1 )] ans = '' ansLen = 0 # find length of non-overlapping # substrings for all pairs (i j) for i in range ( n - 1 - 1 - 1 ): for j in range ( n - 1 i - 1 ): # if characters match set value # and compare with ansLen. if s [ i ] == s [ j ]: dp [ i ][ j ] = 1 + min ( dp [ i + 1 ][ j + 1 ] j - i - 1 ) if dp [ i ][ j ] >= ansLen : ansLen = dp [ i ][ j ] ans = s [ i : i + ansLen ] return ans if ansLen > 0 else '-1' if __name__ == '__main__' : s = 'geeksforgeeks' print ( longestSubstring ( s ))
C# // C# program to find longest repeating // and non-overlapping substring // using tabulation using System ; class GfG { static string longestSubstring ( string s ) { int n = s . Length ; int [] dp = new int [ n + 1 n + 1 ]; string ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j > i ; j -- ) { // if characters match set value // and compare with ansLen. if ( s [ i ] == s [ j ]) { dp [ i j ] = 1 + Math . Min ( dp [ i + 1 j + 1 ] j - i - 1 ); if ( dp [ i j ] >= ansLen ) { ansLen = dp [ i j ]; ans = s . Substring ( i ansLen ); } } } } return ansLen > 0 ? ans : '-1' ; } static void Main ( string [] args ) { string s = 'geeksforgeeks' ; Console . WriteLine ( longestSubstring ( s )); } }
JavaScript // JavaScript program to find longest repeating // and non-overlapping substring // using tabulation function longestSubstring ( s ) { const n = s . length ; const dp = Array . from ({ length : n + 1 } () => Array ( n + 1 ). fill ( 0 )); let ans = '' ; let ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( let i = n - 1 ; i >= 0 ; i -- ) { for ( let j = n - 1 ; j > i ; j -- ) { // if characters match set value // and compare with ansLen. if ( s [ i ] === s [ j ]) { dp [ i ][ j ] = 1 + Math . min ( dp [ i + 1 ][ j + 1 ] j - i - 1 ); if ( dp [ i ][ j ] >= ansLen ) { ansLen = dp [ i ][ j ]; ans = s . substring ( i i + ansLen ); } } } } return ansLen > 0 ? ans : '-1' ; } const s = 'geeksforgeeks' ; console . log ( longestSubstring ( s ));
Producción
geeks
Uso de DP optimizado para el espacio: tiempo O(n^2) y espacio O(n)
C++La idea es utilizar un matriz 1D única en lugar de un matriz 2D haciendo un seguimiento sólo de los 'siguiente fila' valores necesarios para calcular sufijo[i][j]. Dado que cada valor s sufijo[i][j] depende sólo de sufijo[i+1][j+1] en la fila siguiente podemos mantener los valores de la fila anterior en una matriz 1D y actualizarlos iterativamente para cada fila.
// C++ program to find longest repeating // and non-overlapping substring // using space optimised #include using namespace std ; string longestSubstring ( string s ) { int n = s . length (); vector < int > dp ( n + 1 0 ); string ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (ij) for ( int i = n -1 ; i >= 0 ; i -- ) { for ( int j = i ; j < n ; j ++ ) { // if characters match set value // and compare with ansLen. if ( s [ i ] == s [ j ]) { dp [ j ] = 1 + min ( dp [ j + 1 ] j - i -1 ); if ( dp [ j ] >= ansLen ) { ansLen = dp [ j ]; ans = s . substr ( i ansLen ); } } else dp [ j ] = 0 ; } } return ansLen > 0 ? ans : '-1' ; } int main () { string s = 'geeksforgeeks' ; cout < < longestSubstring ( s ) < < endl ; return 0 ; }
Java // Java program to find longest repeating // and non-overlapping substring // using space optimised class GfG { static String longestSubstring ( String s ) { int n = s . length (); int [] dp = new int [ n + 1 ] ; String ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = i ; j < n ; j ++ ) { // if characters match set value // and compare with ansLen. if ( s . charAt ( i ) == s . charAt ( j )) { dp [ j ] = 1 + Math . min ( dp [ j + 1 ] j - i - 1 ); if ( dp [ j ] >= ansLen ) { ansLen = dp [ j ] ; ans = s . substring ( i i + ansLen ); } } else { dp [ j ] = 0 ; } } } return ansLen > 0 ? ans : '-1' ; } public static void main ( String [] args ) { String s = 'geeksforgeeks' ; System . out . println ( longestSubstring ( s )); } }
Python # Python program to find longest repeating # and non-overlapping substring # using space optimised def longestSubstring ( s ): n = len ( s ) dp = [ 0 ] * ( n + 1 ) ans = '' ansLen = 0 # find length of non-overlapping # substrings for all pairs (i j) for i in range ( n - 1 - 1 - 1 ): for j in range ( i n ): # if characters match set value # and compare with ansLen. if s [ i ] == s [ j ]: dp [ j ] = 1 + min ( dp [ j + 1 ] j - i - 1 ) if dp [ j ] >= ansLen : ansLen = dp [ j ] ans = s [ i : i + ansLen ] else : dp [ j ] = 0 return ans if ansLen > 0 else '-1' if __name__ == '__main__' : s = 'geeksforgeeks' print ( longestSubstring ( s ))
C# // C# program to find longest repeating // and non-overlapping substring // using space optimised using System ; class GfG { static string longestSubstring ( string s ) { int n = s . Length ; int [] dp = new int [ n + 1 ]; string ans = '' ; int ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = i ; j < n ; j ++ ) { // if characters match set value // and compare with ansLen. if ( s [ i ] == s [ j ]) { dp [ j ] = 1 + Math . Min ( dp [ j + 1 ] j - i - 1 ); if ( dp [ j ] >= ansLen ) { ansLen = dp [ j ]; ans = s . Substring ( i ansLen ); } } else { dp [ j ] = 0 ; } } } return ansLen > 0 ? ans : '-1' ; } static void Main ( string [] args ) { string s = 'geeksforgeeks' ; Console . WriteLine ( longestSubstring ( s )); } }
JavaScript // JavaScript program to find longest repeating // and non-overlapping substring // using space optimised function longestSubstring ( s ) { const n = s . length ; const dp = new Array ( n + 1 ). fill ( 0 ); let ans = '' ; let ansLen = 0 ; // find length of non-overlapping // substrings for all pairs (i j) for ( let i = n - 1 ; i >= 0 ; i -- ) { for ( let j = i ; j < n ; j ++ ) { // if characters match set value // and compare with ansLen. if ( s [ i ] === s [ j ]) { dp [ j ] = 1 + Math . min ( dp [ j + 1 ] j - i - 1 ); if ( dp [ j ] >= ansLen ) { ansLen = dp [ j ]; ans = s . substring ( i i + ansLen ); } } else { dp [ j ] = 0 ; } } } return ansLen > 0 ? ans : '-1' ; } const s = 'geeksforgeeks' ; console . log ( longestSubstring ( s ));
Producción
geeks
Artículos relacionados:
- Subcadena común más larga
