es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Determinación de la longitud de uno de los palíndromos más largos en una cadena.

19 Jul, 2023 Programación

Tengo que implementar una función que determine la longitud de uno de los palíndromos más largos en una cadena. Las cadenas consisten únicamente de números y letras. Al probar palíndromos, se debe tener en cuenta tanto las mayúsculas como las minúsculas.

Aquí está mi código, pero debería ser más eficiente:

#incluye <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int longitud_palindromo_mas_largo(char str[]) {
int longitud = strlen(str);
int palindromo_mas_largo = 0;

for (int i = 0; i < longitud; i++) {
    for (int x = i; x < longitud; x++) {
        int signo = 1;
        for (int s = 0; s < (x - i + 1) / 2; s++) {
            if (str[i + s] != str[x - s]) signo = 0;
        }
        if (signo && (x - i + 1) > palindromo_mas_largo) {
            palindromo_mas_largo = x - i + 1;
        }
    }
}
return palindromo_mas_largo;

}

int main(void) {

printf("%d\n", longitud_palindromo_mas_largo("öaslkdhfwefjkvneifnkldnlbnlkvsdfnslkdvnaljfslfjsofnslkdfnsfjlskdnvln"));

return EXIT_SUCCESS;

}

Estaría muy agradecido/a por una explicación adicional de tus sugerencias/código sobre cómo sería más eficiente (Un amigo me sugirió probar las partes más grandes de la cadena, pero no llegamos más lejos allí).</math.h></stdio.h></stdlib.h></string.h>

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Una forma de mejorar la eficiencia sería utilizar programación dinámica para almacenar los resultados de cálculos previos y evitar cálculos redundantes. Específicamente, podemos utilizar una tabla bidimensional para almacenar los resultados de comprobar si una subcadena desde el índice i hasta j es un palíndromo.

    La tabla tendría dimensiones longitud x longitud, donde longitud es la longitud de la cadena de entrada. Podemos inicializar la tabla con los casos base donde una subcadena de longitud 1 siempre es un palíndromo y una subcadena de longitud 2 es un palíndromo si sus caracteres son iguales.

    Luego, podemos iterar sobre todas las posibles longitudes de subcadena l desde 3 hasta longitud y comprobar todos los posibles índices de inicio i desde 0 hasta longitud-l. Para cada combinación de l e i, comprobamos si la subcadena correspondiente str[i:i+l-1] es un palíndromo buscando las dos entradas diagonales en la tabla para str[i+1:i+l-2] y comparando los caracteres en las posiciones i e i+l-1.

    Si la cadena es un palíndromo, actualizamos la variable longest_palindrome si su longitud es mayor que el palíndromo más largo actual.

    Aquí está el código actualizado:

    #include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int length_longest_palindrome(char str[]) {
    int length = strlen(str);
    int longest_palindrome = 0;
    int table[length][length]; // tabla de programación dinámica

    // casos base
    for (int i = 0; i < length; i++) {
        table[i][i] = 1; // una subcadena de longitud 1 siempre es un palíndromo
        if (i < length-1) {
            table[i][i+1] = (str[i] == str[i+1]); // una subcadena de longitud 2 es un palíndromo si sus caracteres son iguales
            if (table[i][i+1]) longest_palindrome = 2; // actualizamos longest_palindrome si es necesario
        }
    }

    // comprobamos todas las posibles longitudes de subcadena e índices de inicio
    for (int l = 3; l <= length; l++) {
        for (int i = 0; i <= length-l; i++) {
            int j = i+l-1;
            table[i][j] = (str[i] == str[j]) && table[i+1][j-1]; // comprobamos si la subcadena es un palíndromo
            if (table[i][j] && l > longest_palindrome) longest_palindrome = l; // actualizamos longest_palindrome si es necesario
        }
    }

    return longest_palindrome;
}

int main(void) {
    printf("%d\n", length_longest_palindrome("öaslkdhfwefjkvneifnkldnlbnlkvsdfnslkdvnaljfslfjsofnslkdfnsfjlskdnvln"));
    return EXIT_SUCCESS;
}

    Tenga en cuenta que las principales diferencias con respecto al código original son el uso de la tabla de programación dinámica y los bucles anidados para iterar sobre todas las subcadenas posibles. La complejidad temporal de este algoritmo es O(n^2), donde n es la longitud de la cadena de entrada, lo cual es una mejora significativa con respecto a la complejidad temporal del algoritmo original, que era de O(n^3).</math.h></stdio.h></stdlib.h></string.h>

Comments are closed.