Având în vedere a șir s sarcina este de a găsi cel mai lung subșir care se repetă fără suprapunere în ea. Cu alte cuvinte găsi 2 subșiruri identice de lungime maxima care nu se suprapun. Returnați -1 dacă nu există un astfel de șir.
Nota: Sunt posibile răspunsuri multiple, dar trebuie să returnăm subșir cui prima apariție este mai devreme.
Exemple:
Intrare: s = 'acdcdcdc'
Ieșire: „AC/DC”
Explicaţie: Șirul „acdc” este cel mai lung Subșir de s care se repetă, dar nu se suprapune.Intrare: s = 'geeksforgeeks'
Ieșire: "tocilari"
Explicaţie: Șirul „geeks” este cel mai lung sub șir de s care se repetă, dar nu se suprapune.
Cuprins
- Folosind metoda forței brute - O(n^3) Timp și O(n) Spațiu
- Utilizarea de sus în jos DP (Memoization) - O(n^2) Timp și O(n^2) Spațiu
- Folosind DP de jos în sus (tabulare) - O(n^2) Timp și O(n^2) Spațiu
- Folosind DP optimizat pentru spațiu – O(n^2) Timp și O(n) Spațiu
Folosind metoda forței brute - O(n^3) Timp și O(n) Spațiu
C++Ideea este să genera toate subșiruri posibile și verificați dacă subșirul există în ramanand şir. Dacă subșirul există și acesta lungime este mai mare decât răspunsul subșirului apoi setați răspuns la subșirul curent.
// C++ program to find longest repeating // and non-overlapping substring // using recursion #include
// 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 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# 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 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));
Ieșire
geeks
Utilizarea de sus în jos DP (Memoization) - O(n^2) Timp și O(n^2) Spațiu
Abordarea este de a calcula cel mai lung sufix care se repetă pentru toate prefixele perechi în șir s . Pentru indici i şi j dacă s[i] == s[j] apoi recursiv calcula sufix (i+1 j+1) și setați sufix (i j) ca min(sufix(i+1 j+1) + 1 j - i - 1) la preveni suprapunerea . Dacă personajele nu se potrivesc setați sufixul(i j) = 0.
Nota:
- Pentru a evita suprapunerea trebuie să ne asigurăm că lungimea de sufixul este mai mic decât (j-i) în orice clipă.
- Valoarea maximă a sufix (i j) furnizează lungimea celui mai lung subșir care se repetă, iar subșirul în sine poate fi găsit folosind lungimea și indexul de început al sufixului comun.
- sufix (i j) stochează lungimea celui mai lung sufix comun dintre indici i si j asigurându-l nu depășește j - i - 1 pentru a evita suprapunerea.
// C++ program to find longest repeating // and non-overlapping substring // using memoization #include
// 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 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# 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 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));
Ieșire
geeks
Folosind DP de jos în sus (tabulare) - O(n^2) Timp și O(n^2) Spațiu
C++Ideea este să creați o matrice 2D de dimensiune (n+1)*(n+1) și calculați cele mai lungi sufixe repetate pentru toți indexul perechi (i j) iterativ. Pornim de la Sfârşit de sfoară și lucrați înapoi pentru a umple masa. Pentru fiecare (i j) dacă s[i] == s[j] stabilim sufix[i][j] la min(sufix[i+1][j+1]+1 j-i-1) pentru a evita suprapunerea; altfel sufix [i][j] = 0.
// C++ program to find longest repeating // and non-overlapping substring // using tabulation #include
// 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 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# 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 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));
Ieșire
geeks
Folosind DP optimizat pentru spațiu – O(n^2) Timp și O(n) Spațiu
C++Ideea este de a folosi un o singură matrice 1D în loc de a matrice 2D ținând evidența doar a „rândul următor” valorile necesare pentru calcul sufix[i][j]. Deoarece fiecare valoare s sufix[i][j] depinde doar de sufix[i+1][j+1] în rândul de mai jos putem menține valorile rândului anterior într-o matrice 1D și le putem actualiza iterativ pentru fiecare rând.
// C++ program to find longest repeating // and non-overlapping substring // using space optimised #include
// 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 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# 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 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));
Ieșire
geeks
Articole înrudite:
- Cel mai lung subșir comun