Sous-chaîne la plus longue et sans chevauchement
Essayez-le sur GfG Practice 
Sortir
Sortir
Sortir
Sortir
Compte tenu d'un chaîne s la tâche est de trouver le sous-chaîne sans chevauchement répétitive la plus longue dedans. En d'autres termes, trouver 2 sous-chaînes identiques de longueur maximale qui ne se chevauchent pas. Renvoie -1 si aucune chaîne de ce type n'existe.
Note: Plusieurs réponses sont possibles mais nous devons renvoyer la sous-chaîne dont première occurrence est plus tôt.
Exemples :
Saisir: s = 'acdcdcdc'
Sortir: "AC/DC"
Explication: La chaîne 'acdc' est la plus longue sous-chaîne de s qui se répète mais ne se chevauche pas.Saisir: s = 'geeksforgeeks'
Sortir: 'geeks'
Explication: La chaîne 'geeks' est la sous-chaîne la plus longue de s qui se répète mais ne se chevauche pas.
Table des matières
- Utilisation de la méthode Brute Force - O(n^3) Temps et O(n) Espace
- Utilisation de la DP descendante (mémoisation) – O(n^2) temps et O(n^2) espace
- Utilisation de DP ascendante (tabulation) - O (n ^ 2) Temps et O (n ^ 2) Espace
- Utilisation de DP optimisé pour l'espace – O(n^2) Temps et O(n) Espace
Utilisation de la méthode Brute Force - O(n^3) Temps et O(n) Espace
C++L'idée est de générer tout le sous-chaînes possibles et vérifiez si la sous-chaîne existe dans le restant chaîne. Si la sous-chaîne existe et que son longueur est plus grand que de répondre à la sous-chaîne puis de définir répondre à la sous-chaîne actuelle.
// 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 ));
Sortir
geeks
Utilisation de la DP descendante (mémoïsation) – O(n^2) temps et O(n^2) espace
L'approche consiste à calculer le suffixe répétitif le plus long pour tous les préfixes paires dans le chaîne s . Pour les indices je et j si s[je] == s[j] alors récursivement calculer suffixe(i+1 j+1) et définir suffixe(i j) comme min(suffixe(i+1 j+1) + 1 j - i - 1) à éviter les chevauchements . Si les caractères ne correspondent pas définir le suffixe (i j) = 0.
Note:
- Pour éviter les chevauchements, nous devons veiller à ce que la longueur le suffixe est inférieur à (j-i) à tout instant.
- La valeur maximale de suffixe(i j) fournit la longueur de la sous-chaîne répétitive la plus longue et la sous-chaîne elle-même peut être trouvée en utilisant la longueur et l'index de départ du suffixe commun.
- suffixe(i j) stocke la longueur du suffixe commun le plus long entre les indices moi et j l'assurer ne dépasse pas j - i - 1 pour éviter les chevauchements.
// 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 ));
Sortir
geeks
Utilisation de DP ascendante (tabulation) - O (n ^ 2) Temps et O (n ^ 2) Espace
C++L'idée est de créer une matrice 2D de taille (n+1)*(n+1) et calculez les suffixes répétitifs les plus longs pour tous les index paires (i j) de manière itérative. Nous partons du fin de la chaîne et travaillez à rebours pour remplir le tableau. Pour chacun (je j) si s[je] == s[j] nous définissons suffixe[i][j] à min(suffixe[i+1][j+1]+1 j-i-1) pour éviter les chevauchements ; sinon suffixe[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 ));
Sortir
geeks
Utilisation de DP optimisé pour l'espace – O(n^2) Temps et O(n) Espace
C++L'idée est d'utiliser un tableau 1D unique au lieu d'un matrice 2D en gardant une trace uniquement des 'rangée suivante' valeurs requises pour calculer suffixe[i][j]. Puisque chaque valeur s suffixe[i][j] ne dépend que de suffixe[i+1][j+1] dans la ligne ci-dessous, nous pouvons conserver les valeurs de la ligne précédente dans un tableau 1D et les mettre à jour de manière itérative pour chaque ligne.
// 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 ));
Sortir
geeks
Articles connexes :
- Sous-chaîne commune la plus longue
