Dada una string, encuentre la longitud de la subsecuencia repetida más larga, de modo que las dos subsecuencias no tengan el mismo carácter de string en la misma posición, es decir, cualquier i -ésimo carácter en las dos subsecuencias no debería tener el mismo índice en la string original .
Ejemplos:
Input: str = "abc" Output: 0 There is no repeating subsequence Input: str = "aab" Output: 1 The two subsequence are 'a'(first) and 'a'(second). Note that 'b' cannot be considered as part of subsequence as it would be at same index in both. Input: str = "aabb" Output: 2 Input: str = "axxxy" Output: 2
Este problema es solo la modificación del problema de la subsecuencia común más larga . La idea es encontrar el LCS (str, str) donde str es la string de entrada con la restricción de que cuando ambos caracteres son iguales, no deberían estar en el mismo índice en las dos strings.
Algoritmo:
Paso 1: inicialice la string de entrada, que debe verificarse.
Paso 2: inicialice la longitud de la string en la variable.
Paso 3: Cree una tabla DP utilizando una array 2D y establezca cada elemento en 0.
Paso 4: Complete la tabla si los caracteres son iguales y los índices son diferentes.
Paso 5: Devolver los valores dentro de la tabla
Paso 6: Imprima la string.
A continuación se muestra la implementación de la idea.
C++
// C++ program to find the longest repeating // subsequence #include <iostream> #include <string> using namespace std; // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. int findLongestRepeatingSubSeq(string str) { int n = str.length(); // Create and initialize DP table int dp[n+1][n+1]; for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) dp[i][j] = 0; // Fill dp table (similar to LCS loops) for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { // If characters match and indexes are // not same if (str[i-1] == str[j-1] && i != j) dp[i][j] = 1 + dp[i-1][j-1]; // If characters do not match else dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } return dp[n][n]; } // Driver Program int main() { string str = "aabb"; cout << "The length of the largest subsequence that" " repeats itself is : " << findLongestRepeatingSubSeq(str); return 0; }
Java
// Java program to find the longest // repeating subsequence import java.io.*; import java.util.*; class LRS { // Function to find the longest repeating subsequence static int findLongestRepeatingSubSeq(String str) { int n = str.length(); // Create and initialize DP table int[][] dp = new int[n+1][n+1]; // Fill dp table (similar to LCS loops) for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { // If characters match and indexes are not same if (str.charAt(i-1) == str.charAt(j-1) && i!=j) dp[i][j] = 1 + dp[i-1][j-1]; // If characters do not match else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } return dp[n][n]; } // driver program to check above function public static void main (String[] args) { String str = "aabb"; System.out.println("The length of the largest subsequence that" +" repeats itself is : "+findLongestRepeatingSubSeq(str)); } } // This code is contributed by Pramod Kumar
Python3
# Python 3 program to find the longest repeating # subsequence # This function mainly returns LCS(str, str) # with a condition that same characters at # same index are not considered. def findLongestRepeatingSubSeq( str): n = len(str) # Create and initialize DP table dp=[[0 for i in range(n+1)] for j in range(n+1)] # Fill dp table (similar to LCS loops) for i in range(1,n+1): for j in range(1,n+1): # If characters match and indexes are # not same if (str[i-1] == str[j-1] and i != j): dp[i][j] = 1 + dp[i-1][j-1] # If characters do not match else: dp[i][j] = max(dp[i][j-1], dp[i-1][j]) return dp[n][n] # Driver Program if __name__=='__main__': str = "aabb" print("The length of the largest subsequence that repeats itself is : " ,findLongestRepeatingSubSeq(str)) # this code is contributed by ash264
C#
// C# program to find the longest repeating // subsequence using System; class GFG { // Function to find the longest repeating // subsequence static int findLongestRepeatingSubSeq(string str) { int n = str.Length; // Create and initialize DP table int [,]dp = new int[n+1,n+1]; // Fill dp table (similar to LCS loops) for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // If characters match and indexes // are not same if (str[i-1] == str[j-1] && i != j) dp[i,j] = 1 + dp[i-1,j-1]; // If characters do not match else dp[i,j] = Math.Max(dp[i,j-1], dp[i-1,j]); } } return dp[n,n]; } // driver program to check above function public static void Main () { string str = "aabb"; Console.Write("The length of the largest " + "subsequence that repeats itself is : " + findLongestRepeatingSubSeq(str)); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to find the // longest repeating subsequence // This function mainly returns // LCS(str, str) with a condition // that same characters at same // index are not considered. function findLongestRepeatingSubSeq($str) { $n = strlen($str); // Create and initialize // DP table $dp = array(array()); for ($i = 0; $i <= $n; $i++) for ($j = 0; $j <= $n; $j++) $dp[$i][$j] = 0; // Fill dp table // (similar to LCS loops) for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $n; $j++) { // If characters match and // indexes are not same if ($str[$i - 1] == $str[$j - 1] && $i != $j) $dp[$i][$j] = 1 + $dp[$i - 1][$j - 1]; // If characters // do not match else $dp[$i][$j] = max($dp[$i][$j - 1], $dp[$i - 1][$j]); } } return $dp[$n][$n]; } // Driver Code $str = "aabb"; echo "The length of the largest ". "subsequence that repeats itself is : ", findLongestRepeatingSubSeq($str); // This code is contributed // by shiv_bhakt. ?>
Javascript
<script> // Javascript program to find the longest repeating // subsequence // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. function findLongestRepeatingSubSeq(str) { var n = str.length; // Create and initialize DP table var dp = new Array(n + 1); for (var i=0; i<=n; i++) { dp[i] = new Array(n + 1); for (var j=0; j<=n; j++) { dp[i][j] = 0; } } // Fill dp table (similar to LCS loops) for (var i=1; i<=n; i++) { for (var j=1; j<=n; j++) { // If characters match and indexes are // not same if ((str[i-1] == str[j-1]) && (i != j)) dp[i][j] = 1 + dp[i-1][j-1]; // If characters do not match else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } return dp[n][n]; } // Driver Code var str = "aabb"; document.write("The length of the largest subsequence that repeats itself is : " + findLongestRepeatingSubSeq(str)); </script>
Producción:
The length of the largest subsequence that repeats itself is : 2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n 2 )
Otro enfoque: (usando la recursividad)
C++
// C++ program to find the longest repeating // subsequence using recursion #include <bits/stdc++.h> using namespace std; int dp[1000][1000]; // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. int findLongestRepeatingSubSeq(string X, int m, int n) { if(dp[m][n]!=-1) return dp[m][n]; // return if we have reached the end of either string if (m == 0 || n == 0) return dp[m][n] = 0; // if characters at index m and n matches // and index is different if (X[m - 1] == X[n - 1] && m != n) return dp[m][n] = findLongestRepeatingSubSeq(X, m - 1, n - 1) + 1; // else if characters at index m and n don't match return dp[m][n] = max (findLongestRepeatingSubSeq(X, m, n - 1), findLongestRepeatingSubSeq(X, m - 1, n)); } // Longest Repeated Subsequence Problem int main() { string str = "aabb"; int m = str.length(); memset(dp,-1,sizeof(dp)); cout << "The length of the largest subsequence that" " repeats itself is : " << findLongestRepeatingSubSeq(str,m,m); return 0; // this code is contributed by Kushdeep Mittal }
Java
import java.util.Arrays; // Java program to find the longest repeating // subsequence using recursion public class GFG { static int dp[][] = new int[1000][1000]; // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. static int findLongestRepeatingSubSeq(char X[], int m, int n) { if (dp[m][n] != -1) { return dp[m][n]; } // return if we have reached the end of either string if (m == 0 || n == 0) { return dp[m][n] = 0; } // if characters at index m and n matches // and index is different if (X[m - 1] == X[n - 1] && m != n) { return dp[m][n] = findLongestRepeatingSubSeq(X, m - 1, n - 1) + 1; } // else if characters at index m and n don't match return dp[m][n] = Math.max(findLongestRepeatingSubSeq(X, m, n - 1), findLongestRepeatingSubSeq(X, m - 1, n)); } // Longest Repeated Subsequence Problem static public void main(String[] args) { String str = "aabb"; int m = str.length(); for (int[] row : dp) { Arrays.fill(row, -1); } System.out.println("The length of the largest subsequence that" + " repeats itself is : " + findLongestRepeatingSubSeq(str.toCharArray(), m, m)); } } // This code is contributed by 29AjayKumar
Python3
# Python 3 program to find the longest repeating # subsequence using recursion dp = [[0 for i in range(1000)] for j in range(1000)] # This function mainly returns LCS(str, str) # with a condition that same characters at # same index are not considered. def findLongestRepeatingSubSeq( X, m, n): if(dp[m][n]!=-1): return dp[m][n] # return if we have reached the end of either string if (m == 0 or n == 0): dp[m][n] = 0 return dp[m][n] # if characters at index m and n matches # and index is different if (X[m - 1] == X[n - 1] and m != n): dp[m][n] = findLongestRepeatingSubSeq(X, m - 1, n - 1) + 1 return dp[m][n] # else if characters at index m and n don't match dp[m][n] = max (findLongestRepeatingSubSeq(X, m, n - 1), findLongestRepeatingSubSeq(X, m - 1, n)) return dp[m][n] # Longest Repeated Subsequence Problem if __name__ == "__main__": str = "aabb" m = len(str) dp =[[-1 for i in range(1000)] for j in range(1000)] print( "The length of the largest subsequence that" " repeats itself is : " , findLongestRepeatingSubSeq(str,m,m)) # this code is contributed by # ChitraNayal
C#
//C# program to find the longest repeating // subsequence using recursion using System; public class GFG { static int [,]dp = new int[1000,1000]; // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. static int findLongestRepeatingSubSeq(char []X, int m, int n) { if (dp[m,n] != -1) { return dp[m,n]; } // return if we have reached the end of either string if (m == 0 || n == 0) { return dp[m,n] = 0; } // if characters at index m and n matches // and index is different if (X[m - 1] == X[n - 1] && m != n) { return dp[m,n] = findLongestRepeatingSubSeq(X, m - 1, n - 1) + 1; } // else if characters at index m and n don't match return dp[m,n] = Math.Max(findLongestRepeatingSubSeq(X, m, n - 1), findLongestRepeatingSubSeq(X, m - 1, n)); } // Longest Repeated Subsequence Problem static public void Main() { String str = "aabb"; int m = str.Length; for (int i = 0; i < dp.GetLength(0); i++) for (int j = 0; j < dp.GetLength(1); j++) dp[i, j] = -1; Console.WriteLine("The length of the largest subsequence that" + " repeats itself is : " + findLongestRepeatingSubSeq(str.ToCharArray(), m, m)); } } // This code is contributed by 29AjayKumar
PHP
<?php // PHP program to find the longest repeating // subsequence using recursion $dp = array_fill(0, 1000, array_fill(0, 1000, -1)); // This function mainly returns LCS(str, str) // with a condition that same characters at // same index are not considered. function findLongestRepeatingSubSeq($X, $m, $n) { global $dp; if($dp[$m][$n] != -1) return $dp[$m][$n]; // return if we have reached the end of either string if ($m == 0 || $n == 0) return $dp[$m][$n] = 0; // if characters at index m and n matches // and index is different if ($X[$m - 1] == $X[$n - 1] && $m != $n) return $dp[$m][$n] = findLongestRepeatingSubSeq($X, $m - 1, $n - 1) + 1; // else if characters at index m and n don't match return $dp[$m][$n] = max (findLongestRepeatingSubSeq($X, $m, $n - 1), findLongestRepeatingSubSeq($X, $m - 1, $n)); } // Driver code $str = "aabb"; $m = strlen($str); echo "The length of the largest subsequence". "that repeats itself is : ".findLongestRepeatingSubSeq($str,$m,$m); // this code is contributed by mits ?>
Javascript
<script> let dp=new Array(1000); for(let i=0;i<1000;i++) { dp[i]=new Array(1000); for(let j=0;j<1000;j++) { dp[i][j]=-1; } } function findLongestRepeatingSubSeq(X,m,n) { if (dp[m][n] != -1) { return dp[m][n]; } // return if we have reached the end of either string if (m == 0 || n == 0) { return dp[m][n] = 0; } // if characters at index m and n matches // and index is different if (X[m - 1] == X[n - 1] && m != n) { return dp[m][n] = findLongestRepeatingSubSeq(X, m - 1, n - 1) + 1; } // else if characters at index m and n don't match return dp[m][n] = Math.max(findLongestRepeatingSubSeq(X, m, n - 1), findLongestRepeatingSubSeq(X, m - 1, n)); } let str = "aabb"; let m = str.length; document.write("The length of the largest subsequence that" + " repeats itself is : " + findLongestRepeatingSubSeq(str.split(""), m, m)); // This code is contributed by ab2127 </script>
Producción:
The length of the largest subsequence that repeats itself is : 2
Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Enfoque 3:
Para encontrar la longitud del enfoque descendente de programación dinámica de la subsecuencia de repetición más larga:
- Tome la string de entrada.
- Realice la subsecuencia común más larga donde s1[i]==s1[j] e i!=j.
- Devuelve la longitud.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int lrs(string s1,int i,int j, vector<vector<int>>&dp){ // return if we have reached the //end of either string if(i >= s1.length() || j >= s1.length()) return 0; if(dp[i][j] != -1) return dp[i][j]; // while dp[i][j] is not computed earlier if(dp[i][j] == -1){ // if characters at index m and n matches // and index is different // Index should not match if(s1[i] == s1[j] && i != j) dp[i][j] = 1+lrs(s1, i+1, j+1, dp); // else if characters at index m and n don't match else dp[i][j] = max(lrs(s1, i, j+1, dp), lrs(s1, i+1, j, dp)); } // return answer return dp[i][j]; } // Driver Code int main(){ string s1 = "aabb"; // Reversing the same string string s2 = s1; reverse(s2.begin(),s2.end()); vector<vector<int>>dp(1000,vector<int>(1000,-1)); cout<<"LENGTH OF LONGEST REPEATING SUBSEQUENCE IS : "<<lrs(s1, 0, 0, dp); } // This code is contributed by shinjanpatra
Java
import java.lang.*; import java.io.*; import java.util.*; class GFG { static int lrs(StringBuilder s1, int i, int j, int[][] dp) { if(i >= s1.length() || j >= s1.length()) { return 0; } if(dp[i][j] != -1) { return dp[i][j]; } if(dp[i][j] == -1) { if(s1.charAt(i) == s1.charAt(j) && i != j) { dp[i][j] = 1 + lrs(s1, i + 1, j + 1, dp); } else { dp[i][j] = Math.max(lrs(s1, i, j + 1, dp), lrs(s1, i + 1, j, dp)); } } return dp[i][j]; } // Driver code public static void main (String[] args) { String s1 = "aabb"; StringBuilder input1 = new StringBuilder(); // append a string into StringBuilder input1 input1.append(s1); // reverse StringBuilder input1 input1.reverse(); int[][] dp = new int[1000][1000]; for(int[] row : dp) { Arrays.fill(row, -1); } System.out.println("LENGTH OF LONGEST REPEATING SUBSEQUENCE IS :" + lrs(input1, 0, 0, dp)); } } // This code is contributed by rag2127.
Python3
# Python 3 program to find the longest repeating # subsequence Length # This function mainly returns LRS(str, str,i,j,dp) # with a condition that same characters at # same index are not considered. def lrs(s1, i, j, dp): # return if we have reached the #end of either string if i >= len(s1) or j >= len(s1): return 0 if dp[i][j] != -1: return dp[i][j] # while dp[i][j] is not computed earlier if dp[i][j] == -1: # if characters at index m and n matches # and index is different # Index should not match if s1[i] == s1[j] and i != j: dp[i][j] = 1+lrs(s1, i+1, j+1, dp) # else if characters at index m and n don't match else: dp[i][j] = max(lrs(s1, i, j+1, dp), lrs(s1, i+1, j, dp)) # return answer return dp[i][j] # Driver Code if __name__ == "__main__": s1 = "aabb" # Reversing the same string s2 = s1[::-1] dp =[[-1 for i in range(1000)] for j in range(1000)] print("LENGTH OF LONGEST REPEATING SUBSEQUENCE IS :", lrs(s1, 0, 0, dp)) # this code is contributed by saikumar kudikala
C#
using System; public class GFG{ static int lrs(string s1, int i, int j, int[,] dp) { if(i >= s1.Length || j >= s1.Length) { return 0; } if(dp[i, j] != -1) { return dp[i, j]; } if(dp[i, j] == -1) { if(s1[i] == s1[j] && i != j) { dp[i, j] = 1 + lrs(s1, i + 1, j + 1, dp); } else { dp[i, j] = Math.Max(lrs(s1, i, j + 1, dp), lrs(s1, i + 1, j, dp)); } } return dp[i, j]; } // Driver code static public void Main (){ string s1 = "aabb"; char[] chars = s1.ToCharArray(); Array.Reverse(chars); s1= new String(chars); int[,] dp = new int[1000,1000]; for(int i = 0; i < 1000; i++) { for(int j = 0; j < 1000; j++) { dp[i, j] = -1; } } Console.WriteLine("LENGTH OF LONGEST REPEATING SUBSEQUENCE IS :" + lrs(s1, 0, 0, dp)); } } // This code is contributed by avanitrachhadiya2155
Javascript
<script> function lrs(s1, i, j, dp) { if (i >= s1.length || j >= s1.length) { return 0; } if (dp[i][j] != -1) { return dp[i][j]; } if (dp[i][j] == -1) { if (s1[i] == s1[j] && i != j) { dp[i][j] = 1 + lrs(s1, i + 1, j + 1, dp); } else { dp[i][j] = Math.max(lrs(s1, i, j + 1, dp), lrs(s1, i + 1, j, dp)); } } return dp[i][j]; } // Driver code let s1 = "aabb"; // Append a string into StringBuilder input1 let input1 = s1.split(""); // Reverse StringBuilder input1 input1.reverse(); let dp = new Array(1000); for(let i = 0; i < 1000; i++) { dp[i] = new Array(1000); for(let j = 0; j < 1000; j++) { dp[i][j] = -1; } } document.write("LENGTH OF LONGEST REPEATING " + "SUBSEQUENCE IS :" + lrs(input1, 0, 0, dp)); // This code is contributed by unknown2108 </script>
LENGTH OF LONGEST REPEATING SUBSEQUENCE IS : 2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA