logo

TechCodeview

A leghosszabb ismétlődő és nem átfedő részkarakterlánc

Próbáld ki a GfG Practice-n ' title=

Adott a string s a feladat megtalálni a leghosszabb ismétlődő, nem átfedő részkarakterlánc benne. Más szóval találni 2 egyforma részkarakterlánc -ból maximális hossza amelyek nem fedik egymást. Ha nem létezik ilyen karakterlánc, adja vissza a -1-et.

Jegyzet:  Több válasz is lehetséges, de vissza kell adnunk a részkarakterlánc akinek  első előfordulása korábbi.

Példák:  



Bemenet:  s = 'acdcdcdc'
Kimenet: "AC/DC"
Magyarázat: Az 'acdc' karakterlánc az s leghosszabb részkarakterlánca, amely ismétlődik, de nem fedi egymást.

Bemenet: s = 'geeksforgeeks'
Kimenet: "geek"
Magyarázat: A 'geeks' karakterlánc az s leghosszabb alkarakterlánca, amely ismétlődik, de nem fedi egymást.

Tartalomjegyzék

Brute Force Method használata - O(n^3) idő és O(n) tér

Az ötlet az, hogy generálni az összes lehetséges részkarakterláncok és ellenőrizze, hogy az alkarakterlánc létezik-e a többi húr. Ha létezik részkarakterlánc, és annak hossz van nagyobb mint válasz részkarakterlánc, majd állítsa be válasz az aktuális részkarakterlánchoz.

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

Kimenet 
geeks

Felülről lefelé irányuló DP (emlékeztető) használata – O(n^2) idő és O(n^2) tér

A megközelítés a leghosszabb ismétlődő utótag az összes előtaghoz párok a string s . Az indexekhez én és j ha s[i] == s[j] majd rekurzív módon kiszámítani utótag (i+1 j+1) és állítsa be utótag (i j) mint min(utótag(i+1 j+1) + 1 j - i - 1) hogy megakadályozza az átfedést . Ha a karakterek nem egyeznek állítsa be az utótagot (i j) = 0.

Jegyzet:

  • Az átfedés elkerülése érdekében ügyelnünk kell arra, hogy a hossza utótag kisebb, mint (j-i) bármelyik pillanatban. 
  • A maximális értéke utótag (i j) megadja a leghosszabb ismétlődő részkarakterlánc hosszát, és maga a részkarakterlánc is megtalálható a közös utótag hosszának és kezdő indexének segítségével.
  • utótag (i j) tárolja az indexek közötti leghosszabb közös utótag hosszát i és j biztosítva azt nem haladja meg a j - i - 1 értéket az átfedés elkerülése érdekében.
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));

Kimenet 
geeks

Alulról felfelé mutató DP (táblázat) használata – O(n^2) idő és O(n^2) tér

Az ötlet az, hogy hozzon létre egy 2D mátrixot -ból méret (n+1)*(n+1) és kiszámítja az összes index leghosszabb ismétlődő utótagját pár (i j) iteratívan. Kezdjük a vége a karakterláncból, és dolgozzon hátrafelé, hogy kitöltse a táblázatot. Mindegyikre (i j) ha s[i] == s[j] beállítjuk utótag[i][j] - min(utótag[i+1][j+1]+1 j-i-1) az átfedés elkerülése érdekében; egyébként utótag[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));

Kimenet 
geeks

Téroptimalizált DP használata – O(n^2) idő és O(n) tér

Az ötlet az, hogy a egyetlen 1D tömb helyett a 2D mátrix csak az 'következő sor' kiszámításához szükséges értékeket utótag[i][j]. Mivel minden érték s utótag[i][j] csak attól függ utótag[i+1][j+1] az alábbi sorban megőrizhetjük az előző sor értékeit egy 1D tömbben, és iteratív módon frissíthetjük őket soronként.

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

Kimenet 
geeks

Kapcsolódó cikkek: 

  • Leghosszabb közös részkarakterlánc