logo

TechCodeview

Længste gentagende og ikke-overlappende understreng

Prøv det på GfG Practice ' title=

Givet en streng s opgaven er at finde længste gentagne ikke-overlappende understreng i den. Find med andre ord 2 identiske understrenge af maksimal længde som ikke overlapper hinanden. Returner -1 hvis der ikke findes en sådan streng.

Note:  Flere svar er mulige, men vi skal returnere understreng hvis  første hændelse er tidligere.

Eksempler:  



Input:  s = 'acdcdcdc'
Produktion: 'AC/DC'
Forklaring: Strengen 'acdc' er den længste understreng af s, som gentager sig, men ikke overlapper.

Input: s = 'geeksforgeeks'
Produktion: 'nørder'
Forklaring: Strengen 'nørder' er den længste understreng af s, som gentager sig, men ikke overlapper.

Indholdsfortegnelse

Brug af brute force metode - O(n^3) tid og O(n) rum

Tanken er at frembringe alle de mulige understrenge og kontroller, om understrengen findes i tilbage snor. Hvis understrengen findes og dens længde er større end svar understreng derefter indstillet svar til den aktuelle understreng.

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));

Produktion 
geeks

Brug af Top-Down DP (Memoization) - O(n^2) Tid og O(n^2) Space

Fremgangsmåden er at beregne længste gentagne suffiks for alle præfikser par i streng s . For indekser jeg og j hvis s[i] == s[j] så rekursivt beregne suffiks(i+1 j+1) og sæt suffiks(i j) som min(suffiks(i+1 j+1) + 1 j - i - 1) til forhindre overlapning . Hvis tegnene ikke stemmer overens sæt suffiks(i j) = 0.

Note:

  • For at undgå overlapning skal vi sikre, at længden af suffiks er mindre end (j-i) på ethvert øjeblik. 
  • Den maksimale værdi af suffiks(i j) angiver længden af ​​den længste gentagne understreng, og selve understrengen kan findes ved hjælp af længden og startindekset for det fælles suffiks.
  • suffiks(i j) gemmer længden af ​​det længste fælles suffiks mellem indekser i og j at sikre det ikke overstiger j - i - 1 for at undgå overlapning.
C++ 
// 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));

Produktion 
geeks

Brug af Bottom-Up DP (Tabulering) - O(n^2) Tid og O(n^2) Rum

Tanken er at skabe en 2D matrix af størrelse (n+1)*(n+1) og beregn de længste gentagne suffikser for alle indekser par (i j) iterativt. Vi tager udgangspunkt i ende af snoren og arbejd baglæns for at fylde bordet. For hver (i j) hvis s[i] == s[j] vi sætter suffiks[i][j] til min(suffiks[i+1][j+1]+1 j-i-1) for at undgå overlapning; ellers suffiks[i][j] = 0.

C++ 
// 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));

Produktion 
geeks

Brug af rumoptimeret DP – O(n^2) tid og O(n) mellemrum

Tanken er at bruge en enkelt 1D-array i stedet for en 2D matrix ved kun at holde styr på 'næste række' værdier, der kræves for at beregne suffiks[i][j]. Da hver værdi s uffix[i][j] afhænger kun af suffiks[i+1][j+1] i rækken nedenfor kan vi vedligeholde den foregående rækkes værdier i et 1D-array og opdatere dem iterativt for hver række.

C++ 
// 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+10);    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));

Produktion 
geeks

Relaterede artikler: 

  • Længste fælles understreng