logo

TechCodeview

Ilgiausia pasikartojanti ir nepersidengianti eilutė

Išbandykite GfG praktikoje ' title=

Atsižvelgiant į a styga s užduotis yra surasti ilgiausiai pasikartojanti nepersidengianti poeilutė joje. Kitaip tariant, rasti 2 identiškos poeilutės iš maksimalus ilgis kurios nesutampa. Grąžinkite -1 jei tokios eilutės nėra.

Pastaba:  Galimi keli atsakymai, bet mes turime juos grąžinti poeilutė kurių  pirmas pasireiškimas yra anksčiau.

Pavyzdžiai:  



Įvestis:  s = 'acdcdcdc'
Išvestis: „AC/DC“
Paaiškinimas: Eilutė „acdc“ yra ilgiausia s poeilutė, kuri kartojasi, bet nepersidengia.

Įvestis: s = 'geeksforgeeks'
Išvestis: "geeks"
Paaiškinimas: Eilutė „geeks“ yra ilgiausia s poeilutė, kuri kartojasi, bet nepersidengia.

Turinio lentelė

Brute Force metodo naudojimas – O(n^3) laikas ir O(n) erdvė

Idėja yra generuoti visi galimos poeilutės ir patikrinkite, ar poeilutė yra likę styga. Jei poeilutė egzistuoja ir jos ilgio yra didesnis nei atsakymo poeilutė, tada nustatykite atsakyti į dabartinę eilutę.

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

Išvestis 
geeks

Naudojant iš viršaus į apačią DP (atmintinė) – O(n^2) laikas ir O(n^2) erdvė

Metodas yra apskaičiuoti ilgiausiai pasikartojanti visų priešdėlių priesaga poros styga s . Dėl indeksų i ir j jeigu s[i] == s[j] tada rekursyviai apskaičiuoti priesaga (i+1 j+1) ir nustatyti priesaga (i j) kaip min(priesaga(i+1 j+1) + 1 j – i – 1) į užkirsti kelią persidengimui . Jei simboliai nesutampa nustatyti priesagą(i j) = 0.

Pastaba:

  • Norėdami išvengti persidengimo, turime užtikrinti, kad ilgis priesaga yra mažesnė nei (j-i) bet kuriuo momentu. 
  • Didžiausia vertė priesaga (i j) pateikia ilgiausiai pasikartojančios poeilutės ilgį, o pačią eilutę galima rasti naudojant bendros priesagos ilgį ir pradžios indeksą.
  • priesaga (i j) išsaugo ilgiausios bendros priesagos tarp indeksų ilgį i ir j tai užtikrinant neviršija j - i - 1 kad būtų išvengta persidengimo.
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));

Išvestis 
geeks

Naudojant DP iš apačios į viršų (tabuliavimas) – O(n^2) laikas ir O(n^2) erdvė

Idėja yra sukurti 2D matricą iš dydis (n+1)*(n+1) ir apskaičiuokite ilgiausiai pasikartojančias visų indeksų priesagas poros (i j) iteratyviai. Mes pradedame nuo pabaiga eilutę ir patraukite atgal, kad užpildytumėte lentelę. Kiekvienam (i j) jeigu s[i] == s[j] nustatome priesaga[i][j] iki min(priesaga[i+1][j+1]+1 j-i-1) išvengti persidengimo; kitaip priesaga [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));

Išvestis 
geeks

Naudojant erdvės optimizuotą DP – O(n^2) laikas ir O(n) erdvė

Idėja yra naudoti a vienas 1D masyvas vietoj a 2D matrica stebint tik "kita eilutė" vertes, kurias reikia apskaičiuoti priesaga[i][j]. Kadangi kiekviena reikšmė s priedėlis[i][j] priklauso tik nuo priesaga [i+1][j+1] žemiau esančioje eilutėje galime išlaikyti ankstesnės eilutės reikšmes 1D masyve ir jas atnaujinti kiekvienoje eilutėje.

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

Išvestis 
geeks

Susiję straipsniai: 

  • Ilgiausia bendroji poeilutė