Subsecuencia repetitiva más larga
Dada una cadena, encuentre la longitud de la subsecuencia repetitiva más larga de modo que las dos subsecuencias no tengan el mismo carácter de cadena en la misma posición, es decir, cualquier carácter i-ésimo en las dos subsecuencias no debería tener el mismo índice en la cadena original.
Ejemplos:
- ¿Se aplican las estructuras de datos y algoritmos para C / C ++ a JavaScript?
- ¿Cómo diferenciar entre algoritmos de clasificación internos y externos en términos simples? ¿Cómo se lo explica a los principiantes?
- ¿Cómo calcular la permutación inversa en un estilo de programación funcional?
- Cómo saber si / cuándo puede aplicar la manipulación de bits para resolver un problema
- En programación, ¿un generador de números aleatorios es realmente aleatorio? ¿O son los números aleatorios generados por un algoritmo oculto?
Entrada: str = “abc”
Salida: 0
No hay subsecuencia repetitiva
Entrada: str = “aab”
Salida: 1
Las dos subsecuencias son ‘a’ (primera) y ‘a’ (segunda).
Tenga en cuenta que ‘b’ no puede considerarse como parte de la subsecuencia
ya que estaría en el mismo índice en ambos.
Entrada: str = “aabb”
Salida: 2
Entrada: str = “axxxy”
Salida: 2
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Este problema es solo la modificación del problema de subsecuencia común más larga. La idea es encontrar el LCS (str, str) donde str es la cadena de entrada con la restricción de que cuando ambos caracteres son iguales, no deberían estar en el mismo índice en las dos cadenas.
A continuación se muestra la implementación de C ++ de la idea.
// C++ program to find the longest repeating
// subsequence
#include
#include
using namespace std;
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;
}
