Subcadena palindrómica más larga
En ciencias de la computación , la subcadena palindrómica más larga o el problema del factor simétrico más largo es el problema de encontrar una subcadena contigua de longitud máxima de una cadena dada que también sea un palíndromo.. Por ejemplo, la subcadena palindrómica más larga de "plátanos" es "anana". No se garantiza que la subcadena palindrómica más larga sea única; por ejemplo, en la cadena "abracadabra", no hay una subcadena palindrómica con una longitud mayor que tres, pero hay dos subcadenas palindrómicas con una longitud tres, a saber, "aca" y "ada". En algunas aplicaciones, puede ser necesario devolver todas las subcadenas palindrómicas máximas (es decir, todas las subcadenas que son palíndromas y no pueden extenderse a subcadenas palindrómicas más grandes) en lugar de devolver solo una subcadena o devolver la longitud máxima de una subcadena palindrómica.
Manacher (1975) inventó un algoritmo de tiempo lineal para enumerar todos los palíndromos que aparecen al comienzo de una cadena dada. Sin embargo, como lo observaron, por ejemplo, Apostolico, Breslauer y Galil (1995) , el mismo algoritmo también se puede usar para encontrar todas las subcadenas palindrómicas máximas en cualquier lugar dentro de la cadena de entrada, nuevamente en tiempo lineal. Por lo tanto, proporciona una solución de tiempo lineal al problema de subcadenas palindrómicas más largo. Jeuring (1994) y Gusfield (1997) proporcionaron soluciones alternativas de tiempo lineal , que describieron una solución basada en árboles de sufijos . Los algoritmos paralelos eficientes también son conocidos por el problema. [1]
El problema de la subcadena palindrómica más larga no debe confundirse con el problema diferente de encontrar la subsecuencia palindrómica más larga .
Este algoritmo es más lento que el de Manacher, pero es un buen trampolín para comprender el algoritmo de Manacher. Considera a cada carácter como el centro de un palíndromo y realiza un bucle para determinar el palíndromo más grande con ese centro.
El bucle en el centro de la función solo funciona para palíndromos donde la longitud es un número impar. La función funciona para palíndromos de longitud uniforme modificando la cadena de entrada. El carácter '|' se inserta entre cada carácter de la cadena de entrada y en ambos extremos. Entonces, la entrada "libro" se convierte en "| b | o | o | k |". El palíndromo de longitud par "oo" en "libro" se convierte en el palíndromo de longitud impar "| o | o |".
El tiempo de ejecución de este algoritmo es . El ciclo exterior corre tiempos y el ciclo interior puede correr hasta tiempos.
