Опитайте в GfG Practice 
Изход
Изход
Изход
Изход
Като се има предвид a низ s задачата е да се намери най-дългият повтарящ се незастъпващ се подниз в него. С други думи намери 2 еднакви подниза на максимална дължина които не се припокриват. Върнете -1 ако не съществува такъв низ.
Забележка: Възможни са няколко отговора, но трябва да върнем подниз чийто първо появяване е по-рано.
Примери:
вход: s = "acdcdcdc"
Изход: „AC/DC“
Обяснение: Низът 'acdc' е най-дългият подниз на s, който се повтаря, но не се припокрива.вход: s = 'geeksforgeeks'
Изход: "отрепки"
Обяснение: Низът 'geeks' е най-дългият подниз на s, който се повтаря, но не се припокрива.
Съдържание
- Използване на метода на груба сила - O(n^3) време и O(n) пространство
- Използване на DP отгоре надолу (мемоизация) - O(n^2) време и O(n^2) пространство
- Използване на DP отдолу нагоре (табулиране) - O(n^2) време и O(n^2) пространство
- Използване на оптимизирано пространство DP – O(n^2) време и O(n) пространство
Използване на метода на груба сила - O(n^3) време и O(n) пространство
C++Идеята е да се генерирам всички възможни поднизове и проверете дали поднизът съществува в оставащи низ. Ако поднизът съществува и неговият дължина е по-голямо отколкото отговор подниз след това задайте отговор към текущия подниз.
// 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 ));
Изход
geeks
Използване на DP отгоре надолу (мемоизация) - O(n^2) време и O(n^2) пространство
Подходът е да се изчисли най-дългият повтарящ се суфикс за всички префикси двойки в низ s . За индекси аз и й ако s[i] == s[j] тогава рекурсивно изчисли суфикс (i+1 j+1) и задайте суфикс (i j) като min(суфикс(i+1 j+1) + 1 j - i - 1) към предотвратяване на припокриване . Ако знаците не съвпадат задаване на суфикс (i j) = 0.
Забележка:
- За да избегнем припокриване, трябва да гарантираме, че дължината на наставката е по-малка от (j-i) във всеки момент.
- Максималната стойност на суфикс (i j) осигурява дължината на най-дългия повтарящ се подниз и самият подниз може да бъде намерен с помощта на дължината и началния индекс на общия суфикс.
- суфикс (i j) съхранява дължината на най-дългия общ суфикс между индексите i и j осигуряването му не превишава j - i - 1 за да избегнете припокриване.
// 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 ));
Изход
geeks
Използване на DP отдолу нагоре (табулиране) - O(n^2) време и O(n^2) пространство
C++Идеята е да се създайте 2D матрица на размер (n+1)*(n+1) и изчислете най-дългите повтарящи се суфикси за всички индекси двойки (i j) итеративно. Започваме от край от низа и работете назад, за да попълните таблицата. За всяка (i j) ако s[i] == s[j] задаваме суфикс[i][j] до min(суфикс[i+1][j+1]+1 j-i-1) за избягване на припокриване; иначе суфикс[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 ));
Изход
geeks
Използване на оптимизирано пространство DP – O(n^2) време и O(n) пространство
C++Идеята е да се използва a единичен 1D масив вместо a 2D матрица като следите само на "следващ ред" стойности, необходими за изчисляване суфикс[i][j]. Тъй като всяка стойност s uffix[i][j] зависи само от суфикс[i+1][j+1] в реда по-долу можем да поддържаме стойностите на предишния ред в 1D масив и да ги актуализираме итеративно за всеки ред.
// 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 ));
Изход
geeks
Свързани статии:
- Най-дългият общ подниз
