Encontrar la subcadena palíndromo más larga

En Informática , el problema de la subcadena palindrómica más larga  es el problema de encontrar la subcadena más larga de una cadena dada que sea un palíndromo .. Por ejemplo, la subcadena palindrómica más larga de "banana" es "anana". La subcadena palindrómica más larga no es necesariamente única; por ejemplo, en la cadena "abracadabra" no hay una subcadena palindrómica de más de tres caracteres, pero hay otras que constan de exactamente tres caracteres, a saber, "aka" y "ada". Algunas aplicaciones desean encontrar todas las subcadenas palindrómicas máximas (es decir, todas las subcadenas que son en sí mismas palíndromos y no se pueden agregar a subcadenas palindrómicas más largas) en lugar de devolver solo una subcadena o devolver la longitud máxima de una subcadena palindrómica.

Manacher (1975 ) inventó un algoritmo lineal en el tiempo para enumerar todos los palíndromos al comienzo de una cadena determinada. Sin embargo, como muestran Apostolico, Breslauer & Galil (1995 ), se puede usar el mismo algoritmo para encontrar todas las subcadenas palindrómicas más largas en cualquier lugar de una cadena dada, nuevamente en tiempo lineal. Por lo tanto, proporciona una solución al problema de encontrar la subcadena palindrómica máxima en tiempo lineal. Jeuring (1994 ) y Gusfield (1997 ) han propuesto soluciones temporales lineales alternativas , quienes describieron una solución basada en el uso de árboles de sufijos . También se conocen algoritmos paralelos eficientes para resolver este problema. [una]

El problema de encontrar la subcadena palindrómica más larga no debe confundirse con el problema de encontrar la subsecuencia palindrómica más larga .

Algoritmo de Manager

Para encontrar el palíndromo más largo en una cadena en tiempo lineal, el algoritmo puede usar las siguientes propiedades de los palíndromos y subpalíndromos:

1. El lado izquierdo de un palíndromo es una imagen especular de su lado derecho.
2. (Caso 1) Un tercer palíndromo cuyo centro se encuentra en el lado derecho del primer palíndromo tendrá exactamente la misma longitud que el segundo palíndromo cuyo centro está reflejado en el lado izquierdo si el segundo palíndromo se encuentra dentro del primero, alejándose del límite en menos para un personaje.
3. (Caso 2) Si el segundo palíndromo tiene un borde común con el primer palíndromo, o se extiende más allá de él, se garantiza que la longitud del tercer palíndromo no será menor que la distancia desde su centro hasta el borde derecho del primer palíndromo. Esta longitud es la distancia desde el centro del segundo palíndromo hasta el carácter más a la izquierda del primer palíndromo.
4. Para encontrar la longitud del tercer palíndromo en el caso 2, es necesario comparar los caracteres que siguen al carácter más a la derecha del primer palíndromo con su imagen especular sobre el centro del tercer palíndromo hasta que se agote la cadena o se produzca una desigualdad de se encuentran los caracteres.
5. (Caso 3) Ni el primer ni el segundo palíndromo proporcionan información para determinar la longitud de un cuarto palíndromo cuyo centro se encuentra fuera del límite del primer palíndromo.
6. Por lo tanto, para determinar de izquierda a derecha las longitudes palindrómicas de las subcadenas en una cadena, es deseable tener un palíndromo de referencia (que actúe como el primer palíndromo) cuyos caracteres ocupen las posiciones más a la derecha en la cadena (y por lo tanto el tercer palíndromo en el caso 2 y el cuarto palíndromo en el caso 3 puede sustituir al primer palíndromo, para convertirse en el nuevo palíndromo de referencia).
7. Con respecto a la estimación del tiempo para determinar la longitud palindrómica para cada carácter de la cadena: en el Caso 1 no se realiza ninguna comparación de caracteres, en los Casos 2 y 3 solo los caracteres de la cadena que se encuentran más allá del carácter más a la derecha del palíndromo de referencia son candidatos para comparación (y, por lo tanto, el Caso 3 siempre conduce a un cambio en el palíndromo de referencia cuando el Caso 2 cambia el palíndromo de referencia solo si resulta que la longitud del tercer palíndromo es en realidad mayor que su longitud mínima prometida).
8. Para palíndromos de grado par, el centro se encuentra entre los dos símbolos centrales del palíndromo.

Implementación

Dejar:

• s es una cadena de N caracteres
• s2 es una cadena derivada de s, que consta de N * 2 + 1 elementos, cada elemento corresponde a uno de: N caracteres en s, N-1 espacios entre caracteres y límites, y espacios antes del primero y después del último carácter de la cadena s respectivamente
• Los límites en s2 no son diferentes en términos de encontrar la longitud de un palíndromo
• Sea p una matriz de radios de palíndromo, es decir, la distancia desde el centro a cualquiera de los caracteres más lejanos del palíndromo (es decir, un palíndromo de longitud 3 tiene un radio palindrómico de 1)
• Sea c la posición del centro del palíndromo que contiene el carácter más cercano al extremo derecho de s2 (la longitud de este palíndromo es p[c]*2+1)
• Sea r la posición del límite más a la derecha de este palíndromo (es decir, r = c + p[c])
• Sea i la posición del elemento (es decir, espacio o carácter) en s2 cuyo radio palindrómico se determina, con i siempre ubicado a la derecha de c
• Sea i_mir la imagen especular de i con respecto a c (es decir, {i, i_mir} = {6, 4}, {7, 3}, {8, 2},... cuando c = 5 (por lo tanto, i_mir = c * 2 - i))

Resultado: el palíndromo más largo o el primer carácter de la cadena