De langste herhalende en niet-overlappende subtekenreeks
Probeer het eens op GfG Practice 
Uitvoer
Uitvoer
Uitvoer
Uitvoer
Gegeven een tekenreeks s de taak is om de langste herhalende niet-overlappende subtekenreeks daarin. Met andere woorden vinden 2 identieke substrings van maximale lengte die elkaar niet overlappen. Retourneert -1 als een dergelijke tekenreeks niet bestaat.
Opmerking: Meerdere antwoorden zijn mogelijk, maar we moeten de antwoorden retourneren subtekenreeks waarvan eerste voorkomen is eerder.
Voorbeelden:
Invoer: s = 'acdcdcdc'
Uitgang: 'AC/DC'
Uitleg: De string 'acdc' is de langste substring van s die zich herhaalt maar niet overlapt.Invoer: s = 'geeksforgeeks'
Uitgang: 'nerds'
Uitleg: De string 'geeks' is de langste subString van s die zich herhaalt maar niet overlapt.
Inhoudsopgave
- Brute Force-methode gebruiken - O(n^3) tijd en O(n) ruimte
- DP van bovenaf gebruiken (memoriseren) - O(n^2) tijd en O(n^2) ruimte
- Bottom-up DP gebruiken (tabellering) - O(n^2) tijd en O(n^2) ruimte
- Gebruik van voor ruimte geoptimaliseerde DP – O(n^2) tijd en O(n) ruimte
Brute Force-methode gebruiken - O(n^3) tijd en O(n) ruimte
C++Het idee is om genereren alle mogelijke subreeksen en controleer of de subtekenreeks bestaat in de overig snaar. Als er een subtekenreeks bestaat en de bijbehorende lengte is groter dan de antwoordsubstring en vervolgens instellen antwoord naar de huidige subtekenreeks.
// 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 ));
Uitvoer
geeks
DP van bovenaf gebruiken (memoriseren) - O(n^2) tijd en O(n^2) ruimte
De aanpak is om de langst herhalende achtervoegsel voor alle voorvoegsels paren in de tekenreeks s . Voor indexen i En J als s[ik] == s[j] Dan recursief berekenen achtervoegsel(i+1j+1) en ingesteld achtervoegsel(i j) als min(achtervoegsel(i+1 j+1) + 1 j - i - 1) naar overlap voorkomen . Als de karakters niet overeenkomen stel achtervoegsel(i j) = 0 in.
Opmerking:
- Om overlapping te voorkomen moeten we ervoor zorgen dat de lengte van achtervoegsel is kleiner dan (j-i) op elk moment.
- De maximale waarde van achtervoegsel(i j) geeft de lengte van de langst herhalende subtekenreeks en de subtekenreeks zelf kan worden gevonden met behulp van de lengte en de startindex van het algemene achtervoegsel.
- achtervoegsel(i j) slaat de lengte op van het langste gemeenschappelijke achtervoegsel tussen indices ik en j ervoor zorgen niet groter is dan j - i - 1 om overlap te voorkomen.
// 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 ));
Uitvoer
geeks
Bottom-up DP gebruiken (tabellering) - O(n^2) tijd en O(n^2) ruimte
C++Het idee is om maak een 2D-matrix van maat (n+1)*(n+1) en bereken de langst herhalende achtervoegsels voor alle indexen paren (ik) iteratief. Wij gaan uit van de einde van het touwtje en werk achteruit om de tabel te vullen. Voor elk (ik) als s[ik] == s[j] wij zetten achtervoegsel[i][j] tot min(achtervoegsel[i+1][j+1]+1 j-i-1) om overlap te voorkomen; anders achtervoegsel[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 ));
Uitvoer
geeks
Gebruik van voor ruimte geoptimaliseerde DP – O(n^2) tijd en O(n) ruimte
C++Het idee is om gebruik te maken van een enkele 1D-array in plaats van een 2D-matrix door alleen de 'volgende rij' waarden die nodig zijn om te berekenen achtervoegsel[i][j]. Omdat elke waarde s achtervoegsel[i][j] hangt er alleen van af achtervoegsel[i+1][j+1] in de rij hieronder kunnen we de waarden van de vorige rij in een 1D-array behouden en deze voor elke rij iteratief bijwerken.
// 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 ));
Uitvoer
geeks
Gerelateerde artikelen:
- Langste gemeenschappelijke subtekenreeks
