Determinación de la longitud de uno de los palíndromos más largos en una cadena.
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>
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:
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>