Declaración del problema de LCS: dadas dos secuencias, encuentre la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Por ejemplo, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc son subsecuencias de “abcdefg”. Entonces, una string de longitud n tiene … Continue reading «Programa C++ para la subsecuencia común más larga»
Dada una secuencia, imprima una subsecuencia palindrómica más larga de ella. Ejemplos: Input : BBABCBCAB Output : BABCBAB The above output is the longest palindromic subsequence of given sequence. «BBBBB» and «BBCBB» are also palindromic subsequences of the given sequence, but not the longest ones. Input : GEEKSFORGEEKS Output : Output can be either EEKEE … Continue reading «Imprimir subsecuencia palindrómica más larga»
Dadas dos strings S y Q . La tarea es contar el número de la subsecuencia común en S y T. Ejemplos: Entrada: S = “ajblqcpdz”, T = “aefcnbtdi” Salida: 11 Las subsecuencias comunes son: { “a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ ac”, “cd”, “abd”, “acd” } Entrada: S = “a”, T = … Continue reading «Cuente la subsecuencia común en dos strings»
Dadas dos strings binarias A y B de tamaño N y M respectivamente, la tarea es maximizar el valor de la longitud de (X) / 2 XOR(X, Y) eligiendo dos substrings X e Y de igual longitud de la string dada A y B respectivamente. Ejemplos: Entrada: A = “0110”, B = “1101” Salida: 3 … Continue reading «Maximice [longitud (X)/2^(XOR (X, Y))] eligiendo las substrings X e Y de la string A y B respectivamente»
Dadas dos secuencias P y Q de números. La tarea es encontrar la subsecuencia común más larga de dos secuencias si se nos permite cambiar como máximo el elemento k en la primera secuencia a cualquier valor. Ejemplos: Input : P = { 8, 3 } Q = { 1, 3 } K = 1 … Continue reading «Subsecuencia común más larga con un máximo de k cambios permitidos»
En la distancia de edición estándar, donde se nos permiten 3 operaciones, insertar, eliminar y reemplazar. Considere una variación de la distancia de edición en la que solo se permiten dos operaciones, insertar y eliminar, encuentre la distancia de edición en esta variación. Ejemplos: Input : str1 = «cat», st2 = «cut» Output : 2 … Continue reading «Editar distancia y LCS (Subsecuencia común más larga)»
Dadas dos strings X e Y, y dos valores costX y costY. Necesitamos encontrar el costo mínimo requerido para hacer que las dos strings dadas sean idénticas. Podemos eliminar caracteres de ambas strings. El costo de eliminar un carácter de la string X es costX y de Y es costY. El costo de eliminar todos … Continue reading «Costo mínimo para hacer dos strings idénticas»
Dadas dos strings X , Y y un entero k . Ahora la tarea es convertir la string X con el costo mínimo tal que la subsecuencia común más larga de X e Y después de la conversión sea de longitud k. El costo de la conversión se calcula como XOR del valor del carácter … Continue reading «Costo mínimo para hacer la subsecuencia común más larga de longitud k»
Dada una array A[] que consta de N enteros distintos y otra array B[] que consta de M enteros, la tarea es encontrar el número mínimo de elementos que se agregarán a la array B[] de modo que la array A[] se convierta en el subsecuencia de la array B[] . Ejemplos: Entrada: N = … Continue reading «Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia»
Dadas dos strings A y B de longitudes N y M respectivamente, la tarea es encontrar la longitud de la subsecuencia común más larga que puede ser de dos strings si cualquier carácter de la string A puede intercambiarse con cualquier otro carácter de B cualquier número de veces. Ejemplos: Entrada: A = “abdeff”, B … Continue reading «Subsecuencia común más larga (LCS) mediante el intercambio repetido de caracteres de una string con caracteres de otra string»