С обзиром на а стринг с задатак је пронаћи најдужи понављајући подниз који се не преклапа у њему. Другим речима, пронађите 2 идентична подниза оф максимална дужина који се не преклапају. Врати -1 ако такав низ не постоји.
Напомена: Могуће је дати више одговора, али морамо да вратимо подниз чији прва појава је раније.
Примери:
Улаз: с = 'ацдцдцдц'
Излаз: 'АЦ/ДЦ'
Објашњење: Стринг 'ацдц' је најдужи подниз од с који се понавља, али се не преклапа.Улаз: с = 'геексфоргеекс'
Излаз: 'штребери'
Објашњење: Стринг 'геекс' је најдужи подниз од с који се понавља, али се не преклапа.
Садржај
- Коришћење методе грубе силе – О(н^3) времена и О(н) простора
- Коришћење ДП одозго надоле (мемоизација) – О(н^2) време и О(н^2) простор
- Коришћење ДП одоздо према горе (табулација) - О(н^2) Време и О(н^2) простор
- Коришћење ДП оптимизованог за простор – О(н^2) Време и О(н) Простор
Коришћење методе грубе силе – О(н^3) времена и О(н) простора
C++Идеја је да се генерисати све могући поднизови и проверите да ли подниз постоји у преосталих стринг. Ако подниз постоји и његов дужина је већи него подниз одговора затим поставите одговори на тренутни подниз.
// 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));
Излаз
geeks
Коришћење ДП одозго надоле (мемоизација) – О(н^2) време и О(н^2) простор
Приступ је да се израчуна најдужи суфикс који се понавља за све префиксе парови у стринг с . За индексе и и ј ако с[и] == с[ј] затим рекурзивно израчунати суфикс(и+1 ј+1) и сет суфикс (и ј) као мин(суфикс(и+1 ј+1) + 1 ј - и - 1) да спречити преклапање . Ако се ликови не поклапају поставити суфикс (и ј) = 0.
Напомена:
- Да бисмо избегли преклапање морамо обезбедити да дужина суфикс је мањи од (ј-и) у било ком тренутку.
- Максимална вредност од суфикс (и ј) даје дужину најдужег подниза који се понавља, а сам подниз се може пронаћи коришћењем дужине и почетног индекса заједничког суфикса.
- суфикс (и ј) чува дужину најдужег заједничког суфикса између индекса и и ј обезбеђујући то не прелази ј - и - 1 да би се избегло преклапање.
// 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));
Излаз
geeks
Коришћење ДП одоздо према горе (табулација) - О(н^2) Време и О(н^2) простор
C++Идеја је да се креирајте 2Д матрицу оф величина (н+1)*(н+1) и израчунајте суфиксе који се најдуже понављају за све индексе парови (и ј) итеративно. Почињемо од крај низа и радите уназад да попуните табелу. За сваки (и ј) ако с[и] == с[ј] поставили смо суфикс[и][ј] до мин(суфикс[и+1][ј+1]+1 ј-и-1) да се избегне преклапање; иначе суфикс [и][ј] = 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));
Излаз
geeks
Коришћење ДП оптимизованог за простор – О(н^2) Време и О(н) Простор
C++Идеја је да се користи а један 1Д низ уместо а 2Д матрица праћењем само 'следећи ред' вредности које су потребне за израчунавање суфикс [и][ј]. Пошто свака вредност с уфикс [и][ј] зависи само од суфикс[и+1][ј+1] у реду испод можемо одржавати вредности претходног реда у 1Д низу и ажурирати их итеративно за сваки ред.
// 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));
Излаз
geeks
Повезани чланци:
- Најдужи заједнички подниз