Pisin toistuva ja ei-päällekkäinen osamerkkijono

Kokeile sitä GfG Practicessa ' title=

Koska a merkkijono s tehtävänä on löytää pisin toistuva ei-päällekkäinen osamerkkijono siinä. Toisin sanoen löytää 2 identtistä osamerkkijonoa / enimmäispituus jotka eivät mene päällekkäin. Palauttaa -1 jos tällaista merkkijonoa ei ole.

Huomautus: Useita vastauksia on mahdollista, mutta meidän on palautettava alamerkkijono jonka ensimmäinen esiintyminen on aikaisemmin.

Esimerkkejä:

Syöte: s = 'acdcdcdc'
Lähtö: "AC/DC"
Selitys: Merkkijono 'acdc' on s:n pisin osamerkkijono, joka toistuu mutta ei ole päällekkäinen.
Syöte: s = 'geeksforgeeks'
Lähtö: "nörtti"
Selitys: Merkkijono 'geeks' on s:n pisin osamerkkijono, joka toistuu mutta ei päällekkäin.

Sisällysluettelo

Brute Force -menetelmän käyttäminen - O(n^3) aika ja O(n) avaruus
Ylhäältä alas suuntautuvan DP:n (muistinkäsittely) käyttö – O(n^2) aika ja O(n^2) avaruus
Alhaalta ylöspäin suuntautuvan DP:n käyttäminen (taulukko) - O(n^2) aika ja O(n^2) avaruus
Avaruusoptimoidun DP:n käyttö – O(n^2) aika ja O(n) avaruus

Brute Force -menetelmän käyttäminen - O(n^3) aika ja O(n) avaruus

Ideana on tuottaa kaikki mahdolliset osamerkkijonot ja tarkista, onko alimerkkijono olemassa jäljellä merkkijono. Jos osamerkkijono on olemassa ja sen pituus on suurempi kuin vastaus osamerkkijono sitten aseta vastaus nykyiseen osamerkkijonoon.

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

Lähtö

geeks

Ylhäältä alas suuntautuvan DP:n (muistinkäsittely) käyttö – O(n^2) aika ja O(n^2) avaruus

Lähestymistapa on laskea pisin toistuva pääte kaikille etuliitteille paria merkkijono s . Indekseille i ja j jos s[i] == s[j] sitten rekursiivisesti laskea pääte(i+1 j+1) ja aseta pääte(i j) kuten min(pääte(i+1 j+1) + 1 j - i - 1) to estää päällekkäisyyksiä . Jos merkit eivät täsmää aseta pääte(i j) = 0.

Huomautus:

Päällekkäisyyksien välttämiseksi meidän on varmistettava, että pituus pääte on pienempi kuin (j-i) milloin tahansa.
Suurin arvo pääte(i j) antaa pisimmän toistuvan osamerkkijonon pituuden ja itse osamerkkijono löytyy yhteisen päätteen pituuden ja aloitusindeksin avulla.
pääte(i j) tallentaa pisimmän yhteisen päätteen pituuden indeksien väliin i ja j varmistaa sen ei ylitä j - i - 1 päällekkäisyyksien välttämiseksi.

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

Lähtö

geeks

Alhaalta ylöspäin suuntautuvan DP:n käyttäminen (taulukko) - O(n^2) aika ja O(n^2) avaruus

Ideana on luo 2D-matriisi / koko (n+1)*(n+1) ja laskea pisimmät toistuvat jälkiliitteet kaikille indekseille paria (i j) iteratiivisesti. Aloitamme kohdasta loppu merkkijonosta ja neulo taaksepäin täyttääksesi taulukon. Jokaiselle (i j) jos s[i] == s[j] asetamme pääte[i][j] - min(pääte[i+1][j+1]+1 j-i-1) päällekkäisyyksien välttämiseksi; muuten pääte[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# 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));

Lähtö

geeks

Avaruusoptimoidun DP:n käyttö – O(n^2) aika ja O(n) avaruus

Ajatuksena on käyttää a yksittäinen 1D-taulukko a sijasta 2D matriisi pitämällä kirjaa vain 'seuraava rivi' laskemiseen tarvittavat arvot pääte[i][j]. Koska jokainen arvo s pääte[i][j] riippuu vain pääte[i+1][j+1] alla olevalla rivillä voimme säilyttää edellisen rivin arvot 1D-taulukossa ja päivittää ne iteratiivisesti jokaiselle riville.

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

Lähtö

geeks

Aiheeseen liittyviä artikkeleita:

Pisin yhteinen alimerkkijono