Subcadena palindrómica más larga

Problema de informática

En informática , el problema de la subcadena palindrómica más larga o 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 "bananas" es "anana". No se garantiza que la subcadena palindrómica más larga sea única; por ejemplo, en la cadena "abracadabra", no hay ninguna subcadena palindrómica con una longitud mayor que tres, pero hay dos subcadenas palindrómicas con una longitud de 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 en sí mismas palíndromos y no se pueden extender 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 en tiempo real para listar todos los palíndromos que aparecen al principio de una cadena dada de longitud . Sin embargo, como observaron, por ejemplo, Apostolico, Breslauer y Galil (1995), el mismo algoritmo también se puede utilizar para encontrar todas las subcadenas palindrómicas máximas en cualquier lugar dentro de la cadena de entrada, nuevamente en el tiempo. Por lo tanto, proporciona una solución en tiempo real al problema de la subcadena palindrómica más larga. Jeuring (1994) y Gusfield (1997) proporcionaron soluciones alternativas en tiempo real, quienes describieron una solución basada en árboles de sufijos . Se puede lograr un algoritmo más rápido en el modelo de cálculo de Word RAM si el tamaño del alfabeto de entrada está en . En particular, este algoritmo se ejecuta en el tiempo utilizando el espacio. ^[1] También se conocen algoritmos paralelos eficientes para el problema. ^[2] ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle \sigma }$ ${\displaystyle 2^{o(\log n)}}$ ${\displaystyle O(n\log \sigma /\log n)}$ ${\displaystyle O(n\log \sigma /\log n)}$

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 .

Algoritmo más lento

Este algoritmo es más lento que el de Manacher, pero es un buen punto de partida para comprender el algoritmo de Manacher. Considera 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 cuya longitud es un número impar. La función funciona para palíndromos de longitud par modificando la cadena de entrada. El carácter '|' se inserta entre cada carácter de la cadena de entrada y en ambos extremos. Por lo tanto, la entrada "book" se convierte en "|b|o|o|k|". El palíndromo de longitud par "oo" en "book" se convierte en el palíndromo de longitud impar "|o|o|".

 Palíndromo más largo LENTO(cadena S, cadena S') { // S' == S con un carácter falso (por ejemplo, '|') insertado // entre cada carácter (incluidos los límites exteriores) // El radio del palíndromo más largo centrado en cada lugar en S' // nota: longitud(S') = longitud(PalindromeRadii) = 2 × longitud(S) + 1 matriz PalindromeRadii = [0,...,0]  Centro = 0 mientras Centro < longitud(S') { // Determinar el palíndromo más largo a partir del cual se inicia // en Centro-Radio y yendo a Centro+Radio Radio = 0 mientras Centro-(Radio + 1) >= 0 y Centro+(Radio + 1) < longitud(S') y S'[Centro-(Radio + 1)] = S'[Centro+(Radio + 1)] { Radio = Radio + 1 }  // Guarda el radio del palíndromo más largo de la matriz PalíndromoRadii[Centro] = Radio  Centro = Centro + 1 }   //Se puede demostrar que longest_palindrome_in_S es max(PalindromeRadii). // si S'[i] == '|', PalindromeRadii[i] es par, de lo contrario podrías aumentar PalindromeRadii[i] en 1, // lo que equivale a insertar un '|' extra en cada borde. // Recuerde que un palíndromo centrado en un '|' en S' corresponde a un palíndromo par en S. // si S'[i] != '|', PalindromeRadii[i] es impar (mismo argumento), y corresponde a un palíndromo impar. // En este caso, la longitud del palíndromo // centrado en ese carácter también está x=PalindromeRadii[i], ya que tenemos (x-1)/2 caracteres en cada lado, // más el extra del medio ((x-1)/2*2+1=x) Palíndromo más largo en S = máx. (Radios del palindromo) devuelve el palíndromo más largo en S }

El tiempo de ejecución de este algoritmo es . El bucle externo se ejecuta veces y el bucle interno puede ejecutarse hasta veces. ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle n/2}$

Algoritmo de Manacher

A continuación se muestra el pseudocódigo del algoritmo de Manacher. El algoritmo es más rápido que el algoritmo anterior porque explota la situación en la que un palíndromo se encuentra dentro de otro palíndromo.

Por ejemplo, considere la cadena de entrada "abacaba". Cuando llegue a la "c", el algoritmo de Manacher habrá identificado la longitud de cada palíndromo centrado en las letras anteriores a la "c". En la "c", ejecuta un bucle para identificar el palíndromo más grande centrado en la "c": "abacaba". Con ese conocimiento, todo lo que está después de la "c" parece el reflejo de todo lo que está antes de la "c". La "a" después de la "c" tiene el mismo palíndromo más largo que la "a" antes de la "c". De manera similar, la "b" después de la "c" tiene un palíndromo más largo que es al menos la longitud del palíndromo más largo centrado en la "b" antes de la "c". Hay algunos casos especiales a considerar, pero ese truco acelera el cálculo drásticamente. ^{[ cita requerida ]}

 Palíndromo más largo (cadena S, cadena S') { // S' == S con un carácter falso (por ejemplo, '|') insertado // entre cada carácter (incluidos los límites exteriores) // El radio del palíndromo más largo centrado en cada lugar en S' // nota: longitud(S') = longitud(PalindromeRadii) = 2 × longitud(S) + 1 matriz PalindromeRadii = [0,...,0]  Centro = 0 Radio = 0  mientras Centro < longitud(S') { // Al comienzo del bucle, Radius ya está establecido en un límite inferior // para el radio más largo. En la primera iteración, el radio es 0, pero // Puede ser mayor en iteraciones posteriores.  // Determinar el palíndromo más largo que comienza en el radio central y // yendo al centro+radio mientras Centro-(Radio+1) >= 0 y Centro+(Radio+1) < longitud(S') y S'[Centro-(Radio+1)] = S'[Centro+(Radio+1)] { Radio = Radio+1 }   // Guarda el radio del palíndromo más largo de la matriz PalíndromoRadii[Centro] = Radio  // A continuación, se incrementa el centro. // Si se pueden reutilizar algunos valores precalculados, se hacen. // Además, el radio puede establecerse en un valor mayor que 0  OldCenter = Centro Radio antiguo = Radio Centro = Centro+1 // El valor predeterminado de Radius será 0, si llegamos al final de la //siguiente bucle. Radio = 0 mientras Centro <= CentroAnterior + RadioAnterior {// Porque el Centro se encuentra dentro del antiguo palíndromo y cada// El carácter dentro de un palíndromo tiene un carácter "reflejado"// reflejada a través de su centro, podemos utilizar los datos que fueron// precalculado para el punto reflejado del Centro. MirroredCenter = OldCenter - (Centro - OldCenter) MaxMirroredRadius = OldCenter + OldRadius - Centro si PalindromeRadii[MirroredCenter] < MaxMirroredRadius { // El palíndromo centrado en MirroredCenter es completamente // contenido en el palíndromo centrado en OldCenter Entonces, // MirroredCenter y Center tienen el mismo tamaño de palíndromo PalíndromoRadio[Centro] = PalíndromoRadio[CentroReflejado] Centro = Centro+1 } de lo contrario si PalindromeRadii[MirroredCenter] > MaxMirroredRadius {  // El palíndromo en MirroredCenter se extiende más allá de la // palíndromo en OldCenter El palíndromo en el Centro debe // termina en el borde del palíndromo OldCenter De lo contrario, // el palíndromo en OldCenter sería más grande PalíndromoRadio[Centro] = MaxMirroredRadius Centro = Centro+1 } else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius // Dado que el palíndromo en MirroredCenter termina exactamente en // el borde del palíndromo centrado en OldCenter, el // El palíndromo en el centro podría ser más grande. Establezca el radio en el // tamaño mínimo del palíndromo en el centro para que no // volver a comprobar innecesariamente Radio = MaxMirroredRadius romper }  }  }// El tamaño de un palíndromo es igual a su radio * 2. Sin embargo, dado que nuestro// La variable Radius considera nuestros caracteres falsos al lado de la// centro, el tamaño de su palíndromo correspondiente es en realidad 2 *// (Radio / 2), lo que significa que el tamaño de un palíndromo es igual a su// valor de radio correspondiente en PalindromeRadii Palíndromo más largo en S = máx. (Radios del palindromo) devuelve el palíndromo más largo en S }

Casos especiales

El algoritmo de Manacher es más rápido porque reutiliza datos precalculados cuando existe un palíndromo dentro de otro palíndromo. Existen tres casos de esto. Están representados por la declaración "if / else if / else" en el pseudocódigo.

El primer caso es cuando el palíndromo en MirroredCenterse encuentra completamente dentro del palíndromo "antiguo". En esta situación, el palíndromo en Centertendrá la misma longitud que el de MirroredCenter. Por ejemplo, si el palíndromo "antiguo" es "abcbpbcba", podemos ver que el palíndromo centrado en la "c" después de la "p" debe tener la misma longitud que el palíndromo centrado en la "c" antes de la "p".

El segundo caso es cuando el palíndromo en MirroredCenterse extiende fuera del palíndromo "Viejo". Es decir, se extiende "hacia la izquierda" (o contiene caracteres con un índice menor que cualquiera dentro del palíndromo "Viejo"). Debido a que el palíndromo "Viejo" es el palíndromo más grande posible centrado en OldCenter, sabemos que los caracteres antes y después de él son diferentes. Por lo tanto, el palíndromo en Centerse extenderá exactamente hasta el borde del palíndromo "Viejo", porque el siguiente carácter será diferente al que está dentro del palíndromo en MirroredCenter. Por ejemplo, si la cadena era "ababc", el palíndromo "Viejo" podría ser "bab" con el Centersiendo el segundo "b" y el MirroredCentersiendo el primer "b". Dado que el palíndromo en MirroredCenteres "aba" y se extiende más allá de los límites del palíndromo "Viejo", sabemos que el palíndromo más largo en el segundo "b" solo puede extenderse hasta el borde del palíndromo "Viejo". Sabemos esto porque si el carácter después del palíndromo "Viejo" hubiera sido una "a" en lugar de una "c", el palíndromo "Viejo" habría sido más largo.

El tercer y último caso es cuando el palíndromo en MirroredCenterse extiende exactamente hasta el borde del palíndromo "Old". En este caso, no sabemos si el carácter después del palíndromo "Old" puede hacer que el palíndromo en sea Centermás largo que el de MirroredCenter. Pero sí sabemos que el palíndromo en Centeres al menos tan largo como el de MirroredCenter. En este caso, Radiusse inicializa con el radio del palíndromo en MirroredCentery la búsqueda comienza desde allí. Un ejemplo de cadena sería "abcbpbcbp", donde el palíndromo "Old" es "bcbpbcb" y el Centerestá en la segunda "c". El MirroredCenteres la primera "c" y tiene un palíndromo más largo de "bcb". El palíndromo más largo en el Centeren la segunda "c" tiene que ser al menos así de largo y, en este caso, es más largo.

Tiempo de ejecución

El algoritmo se ejecuta en tiempo lineal. Esto se puede ver al notar que Centerstrictly aumenta después de cada bucle externo y la suma Center + Radiusno es decreciente. Además, el número de operaciones en el primer bucle interno es lineal en el aumento de la suma Center + Radius, mientras que el número de operaciones en el segundo bucle interno es lineal en el aumento de Center. Como Center ≤ 2n+1y Radius ≤ n, el número total de operaciones en el primer y segundo bucle interno es y el número total de operaciones en el bucle externo, distintas de las de los bucles internos, también es . Por lo tanto, el tiempo de ejecución total es . ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

Notas

1. Charalampopoulos, Panagiotis; Pissis, Solon P.; Radoszewski, Jakub (junio de 2022). Bannai, Hideo; Holub, Jan (eds.). Subcadena palindrómica más larga en tiempo sublineal . Coincidencia de patrones combinatorios. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 223. Schloss Dagstuhl. doi : 10.4230/LIPIcs.CPM.2022.20 .Aquí: Teorema 1, p.20:2.
2. Crochemore y Rytter (1991), Apostolico, Breslauer y Galil (1995).

Véase también

• Árbol palíndromo

Referencias

• Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), "Detección paralela de todos los palíndromos en una cadena", Theoretical Computer Science , 141 (1–2): 163–173, doi : 10.1016/0304-3975(94)00083-U.
• Charalampopoulos, Panagiotis; Pissis, Solon P.; Radoszewski, Jakub (2022), "La subcadena palindrómica más larga en tiempo sublineal", 33.° simposio anual sobre correspondencia de patrones combinatorios, CPM 2022, 27-29 de junio de 2022, Praga, República Checa , 223 : 20:1–20:9, doi : 10.4230/LIPIcs.CPM.2022.20.
• Crochemore, Maxime; Rytter, Wojciech (1991), "Utilidad del algoritmo Karp–Miller–Rosenberg en cálculos paralelos sobre cadenas y matrices", Theoretical Computer Science , 88 (1): 59–82, doi : 10.1016/0304-3975(91)90073-B , MR  1130372.
• Crochemore, Maxime; Rytter, Wojciech (2003), "8.1 Búsqueda de palabras simétricas", Joyas de la cuerdalogía: algoritmos de texto , World Scientific, págs. 111–114, ISBN 978-981-02-4897-0.
• Gusfield, Dan (1997), "9.2 Encontrar todos los palíndromos máximos en tiempo lineal", Algorithms on Strings, Trees, and Sequences , Cambridge: Cambridge University Press, págs. 197-199, doi :10.1017/CBO9780511574931, ISBN 0-521-58519-8, Sr.  1460730.
• Jeuring, Johan (1994), "La derivación de algoritmos en línea, con una aplicación para encontrar palíndromos", Algorithmica , 11 (2): 146–184, doi :10.1007/BF01182773, hdl : 1874/20926 , MR  1272521, S2CID  7032332.
• Manacher, Glenn (1975), "Un nuevo algoritmo "en línea" de tiempo lineal para encontrar el palíndromo inicial más pequeño de una cadena", Journal of the ACM , 22 (3): 346–351, doi : 10.1145/321892.321896 , S2CID  10615419.
•  Este artículo incorpora el texto de la subcadena palindrómica más larga disponible bajo la licencia CC BY 3.0.

Enlaces externos

• Subcadena palindrómica más larga, parte II, 2011-11-20, archivado desde el original el 2018-12-08. Una descripción del algoritmo de Manacher para encontrar la subcadena palindrómica más larga en tiempo lineal.
• Akalin, Fred (2007-11-28), Encontrar la subcadena palindrómica más larga en tiempo lineal , consultado el 2016-10-01Una explicación e implementación en Python del algoritmo de tiempo lineal de Manacher.
• Jeuring, Johan (2007–2010), Palíndromos , consultado el 22 de noviembre de 2011Implementación de Haskell del algoritmo de tiempo lineal de Jeuring.
• Palíndromos(enlace muerto). Implementación en Java del algoritmo de tiempo lineal de Manacher.