Donat a corda s la tasca és trobar el subcadena no solapada que es repeteix més llargament en ell. En altres paraules, trobar 2 subcadenes idèntiques de longitud màxima que no es superposen. Torna -1 si no existeix aquesta cadena.
Nota: Són possibles múltiples respostes, però hem de retornar el subcadena de qui primera aparició és anterior.
Exemples:
Entrada: s = 'acdcdcdc'
Sortida: "AC/DC"
Explicació: La cadena 'acdc' és la subcadena més llarga de s que es repeteix però no es solapa.Entrada: s = 'geeksforgeeks'
Sortida: 'frikis'
Explicació: La cadena "geeks" és la subcadena més llarga de s que es repeteix però no es solapa.
Taula de continguts
- Utilitzant el mètode de la força bruta: O(n^3) Temps i O(n) Espai
- Ús de DP de dalt a baix (memoització) - O(n^2) temps i O(n^2) espai
- Ús de DP de baix a dalt (tabulació) - O (n ^ 2) temps i O (n ^ 2) espai
- Ús d'espai optimitzat DP – O(n^2) Temps i O(n) Espai
Utilitzant el mètode de la força bruta - O(n^3) Temps i O(n) Espai
C++La idea és fer generar tots els possibles subcadenes i comproveu si la subcadena existeix al fitxer restant corda. Si existeix una subcadena i la seva longitud és més gran que respondre a la subcadena i després establir resposta a la subcadena actual.
// 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));
Sortida
geeks
Ús de DP de dalt a baix (memoització) - O(n^2) temps i O(n^2) espai
L'enfocament és calcular el el sufix repetitiu més llarg per a tots els prefixos parelles a la corda s . Per als índexs i i j si s[i] == s[j] aleshores recursivament calcular sufix (i+1 j+1) i posat sufix (i j) com min(sufix(i+1 j+1) + 1 j - i - 1) a evitar la superposició . Si els personatges no coincideixen estableix el sufix (i j) = 0.
Nota:
- Per evitar solapaments hem d'assegurar-nos que la longitud de el sufix és menor que (j-i) en qualsevol instant.
- El valor màxim de sufix (i j) proporciona la longitud de la subcadena repetida més llarga i la subcadena en si es pot trobar utilitzant la longitud i l'índex inicial del sufix comú.
- sufix (i j) emmagatzema la longitud del sufix comú més llarg entre els índexs i i j assegurant-ho no supera j - i - 1 per evitar la superposició.
// 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));
Sortida
geeks
Ús de DP de baix a dalt (tabulació) - O (n ^ 2) temps i O (n ^ 2) espai
C++La idea és fer crear una matriu 2D de mida (n+1)*(n+1) i calculeu els sufixos repetits més llargs per a tots els índexs parells (i j) iterativament. Comencem des del final de la corda i treballeu cap enrere per omplir la taula. Per a cadascun (i j) si s[i] == s[j] establim sufix[i][j] a min(sufix[i+1][j+1]+1 j-i-1) per evitar la superposició; en cas contrari 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));
Sortida
geeks
Ús d'espai optimitzat DP – O(n^2) Temps i O(n) Espai
C++La idea és utilitzar a matriu 1D única en lloc d'a matriu 2D fent un seguiment només de la "fila següent" valors necessaris per calcular sufix[i][j]. Atès que cada valor s sufix[i][j] depèn només de sufix[i+1][j+1] a la fila de sota podem mantenir els valors de la fila anterior en una matriu 1D i actualitzar-los iterativament per a cada fila.
// 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));
Sortida
geeks
Articles relacionats:
- Subcadena comuna més llarga