Algoritmo de Manacher – Substring palindrómica más larga de tiempo lineal – Parte 1

Dada una string, encuentra la substring más larga que es palíndromo. 

• si la string dada es «forgeeksskeegfor», la salida debería ser «geeksskeeg»
• si la string dada es «abaaba», la salida debe ser «abaaba»
• si la string dada es «abababa», la salida debería ser «abababa»
• si la string dada es «abcbabcbabcba», la salida debería ser «abcbabcbabcba»

Ya hemos discutido los enfoques Naïve [O(n ³ )] y cuadrático [O(n ² )] en el Conjunto 1 y el Conjunto 2 . 
En este artículo, hablaremos sobre el algoritmo de Manacher que encuentra la substring palindrómica más larga en tiempo lineal. 
Una forma ( Conjunto 2 ) de encontrar un palíndromo es comenzar desde el centro de la string y comparar los caracteres en ambas direcciones uno por uno. Si los caracteres correspondientes en ambos lados (izquierda y derecha del centro) coinciden, formarán un palíndromo. 
Consideremos la string «abababa». 
Aquí el centro de la string es el cuarto carácter (con índice 3) b. Si hacemos coincidir los caracteres a la izquierda y a la derecha del centro, todos los caracteres coinciden y, por lo tanto, la string «abababa» es un palíndromo. 
  

Aquí, la posición central no es solo la posición real del carácter de la string, sino que también podría ser la posición entre dos caracteres. 
Considere la string «abaaba» de longitud uniforme. Esta string es un palíndromo alrededor de la posición entre los caracteres 3 y 4 a y a respectivamente. 
 

Para encontrar la substring palindrómica más larga de una string de longitud N, una forma es tomar cada uno de los 2*N + 1 centros posibles (las N posiciones de caracteres, N-1 entre dos posiciones de caracteres y 2 posiciones en los extremos izquierdo y derecho), hacer el carácter haga coincidir en las direcciones izquierda y derecha en cada centro 2 * N + 1 y realice un seguimiento de LPS. Este enfoque requiere tiempo O(N^2) y eso es lo que estamos haciendo en el Conjunto 2 . 

Consideremos dos strings «abababa» y «abaaba» como se muestra a continuación:  

En estas dos cuerdas, los lados izquierdo y derecho de las posiciones centrales (posición 7 en la 1ra cuerda y posición 6 en la 2da cuerda) son simétricos. ¿Por qué? Porque toda la cuerda es palíndromo alrededor de la posición central. 
Si necesitamos calcular la substring palindrómica más larga en cada posición 2*N+1 de izquierda a derecha, entonces la propiedad simétrica del palíndromo podría ayudar a evitar algunos de los cálculos innecesarios (es decir, la comparación de caracteres). Si hay un palíndromo de cierta longitud L centrado en cualquier posición P, es posible que no necesitemos comparar todos los caracteres en el lado izquierdo y derecho en la posición P+1. Ya calculamos LPS en posiciones anteriores a P y pueden ayudar a evitar algunas de las comparaciones posteriores a la posición P. 
Este uso de información de posiciones anteriores en un momento posterior hace que el algoritmo de Manacher sea lineal. EnConjunto 2 , no hay reutilización de la información anterior, por lo que es cuadrático. 

El algoritmo de Manacher probablemente se considere complejo de entender, por lo que aquí lo discutiremos de la manera más detallada posible. Algunas de sus partes pueden requerir múltiples lecturas para entenderlas correctamente. 

Veamos la string «abababa». En la tercera figura anterior, se muestran 15 posiciones centrales. Necesitamos calcular la longitud de la cuerda palindrómica más larga en cada una de estas posiciones. 

• En la posición 0, no hay LPS en absoluto (no hay carácter en el lado izquierdo para comparar), por lo que la longitud de LPS será 0.
• En la posición 1, LPS es a, por lo que la longitud de LPS será 1.
• En la posición 2, no hay LPS en absoluto (los caracteres izquierdo y derecho a y b no coinciden), por lo que la longitud de LPS será 0.
• En la posición 3, LPS es aba, por lo que la longitud de LPS será 3.
• En la posición 4, no hay ningún LPS (los caracteres b y a de la izquierda y la derecha no coinciden), por lo que la longitud del LPS será 0.
• En la posición 5, LPS es ababa, por lo que la longitud de LPS será 5.

…… y así 

Almacenamos todas estas longitudes palindrómicas en una array, digamos L. Luego, la string S y LPS Longitud L se ven a continuación:  

De manera similar, la longitud LPS L de la string «abaaba» se verá así: 

En la array LPS L: 

• El valor de longitud LPS en posiciones impares (las posiciones reales de los caracteres) será impar y mayor o igual a 1 (1 provendrá del propio carácter central si nada más coincide en el lado izquierdo y derecho del mismo)
• El valor de longitud de LPS en posiciones pares (las posiciones entre dos caracteres, posiciones extremas izquierda y derecha) será par y mayor o igual a 0 (0 aparecerá cuando no haya coincidencia en el lado izquierdo y derecho)

La posición y el índice de la string son dos cosas diferentes aquí. Para una string S dada de longitud N, los índices serán de 0 a N-1 (total de N índices) y las posiciones serán de 0 a 2*N (total de 2*N+1 posiciones). 

El valor de longitud LPS se puede interpretar de dos maneras, una en términos de índice y la segunda en términos de posición. El valor LPS d en la posición I (L[i] = d) dice que: 

• La substring desde la posición id hasta i+d es un palíndromo de longitud d (en términos de posición)
• La substring del índice (id)/2 a [(i+d)/2 – 1] es un palíndromo de longitud d (en términos de índice)

por ejemplo, en la string «abaaba», L[3] = 3 significa que la substring desde la posición 0 (3-3) hasta la 6 (3+3) es un palíndromo que es «aba» de longitud 3, también significa que la substring del índice 0 [(3-3)/2] a 2 [(3+3)/2 – 1] es un palíndromo que es “aba” de longitud 3.  

Ahora la tarea principal es calcular la array LPS de manera eficiente. Una vez que se calcula esta array, el LPS de la string S se centrará en la posición con el valor máximo de longitud de LPS. 
Lo veremos en la Parte 2 . 

Este artículo es una contribución de Anurag Singh . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.