Najdlhší opakujúci sa a neprekrývajúci sa podreťazec
Vyskúšajte to na GfG Practice 
Výstup
Výstup
Výstup
Výstup
Vzhľadom na a reťazec s úlohou je nájsť najdlhší opakujúci sa neprekrývajúci sa podreťazec v ňom. Inými slovami nájsť 2 rovnaké podreťazce z maximálna dĺžka ktoré sa neprekrývajú. Ak takýto reťazec neexistuje, vráťte -1.
Poznámka: Viaceré odpovede sú možné, ale musíme ich vrátiť podreťazec ktorých prvý výskyt je skôr.
Príklady:
Vstup: s = 'acdcdcdc'
výstup: 'AC/DC'
Vysvetlenie: Reťazec 'acdc' je najdlhší podreťazec s, ktorý sa opakuje, ale neprekrýva sa.Vstup: s = 'geeksforgeeks'
výstup: 'geeks'
Vysvetlenie: Reťazec 'geeks' je najdlhší podreťazec s, ktorý sa opakuje, ale neprekrýva sa.
Obsah
- Použitie metódy hrubej sily - O(n^3) času a O(n) priestoru
- Použitie DP zhora nadol (zapamätanie) – O(n^2) Čas a O(n^2) Priestor
- Použitie DP zdola nahor (tabuľka) - O(n^2) Čas a O(n^2) Priestor
- Použitie priestorovo optimalizovaného DP – O(n^2) času a O(n) priestoru
Použitie metódy hrubej sily - O(n^3) času a O(n) priestoru
C++Myšlienka je generovať všetky možné podreťazce a skontrolujte, či podreťazec existuje v zostávajúce reťazec. Ak existuje podreťazec a jeho dĺžka je väčší než odpoveď podreťazec potom nastavte odpoveď na aktuálny podreťazec.
// 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 ));
Výstup
geeks
Použitie DP zhora nadol (zapamätanie) – O(n^2) Čas a O(n^2) Priestor
Prístup je vypočítať najdlhšia opakujúca sa prípona pre všetky predpony párov v reťazec s . Pre indexy i a j ak s[i] == s[j] potom rekurzívne vypočítať prípona (i+1 j+1) a nastaviť prípona (i j) ako min(prípona(i+1 j+1) + 1 j - i - 1) do zabrániť prekrývaniu . Ak sa znaky nezhodujú nastaviť príponu (i j) = 0.
Poznámka:
- Aby sme sa vyhli prekrývaniu, musíme zabezpečiť, aby dĺžka prípona je menšia ako (j-i) v každom okamihu.
- Maximálna hodnota prípona (i j) poskytuje dĺžku najdlhšieho opakujúceho sa podreťazca a samotný podreťazec možno nájsť pomocou dĺžky a počiatočného indexu spoločnej prípony.
- prípona (i j) ukladá dĺžku najdlhšej spoločnej prípony medzi indexmi ja a j zabezpečenie nepresahuje j - i - 1 aby sa predišlo prekrývaniu.
// 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 ));
Výstup
geeks
Použitie DP zdola nahor (tabuľka) - O(n^2) Čas a O(n^2) Priestor
C++Myšlienka je vytvoriť 2D maticu z veľkosť (n+1)*(n+1) a vypočítajte najdlhšie sa opakujúce prípony pre všetky indexy páry (i j) iteratívne. Začíname od koniec struny a postupujte smerom dozadu, aby ste vyplnili tabuľku. Pre každého (i j) ak s[i] == s[j] nastavili sme prípona[i][j] na min(prípona[i+1][j+1]+1 j-i-1) aby sa zabránilo prekrývaniu; inak prípona[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 ));
Výstup
geeks
Použitie priestorovo optimalizovaného DP – O(n^2) času a O(n) priestoru
C++Cieľom je použiť a jediné 1D pole namiesto a 2D matica sledovaním iba toho 'ďalší riadok' hodnoty potrebné na výpočet prípona[i][j]. Keďže každá hodnota s prípona[i][j] závisí len od prípona[i+1][j+1] v riadku nižšie môžeme zachovať hodnoty predchádzajúceho riadka v 1D poli a aktualizovať ich iteratívne pre každý riadok.
// 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 ));
Výstup
geeks
Súvisiace články:
- Najdlhší spoločný podreťazec
