Algoritmo de Manacher - Encontrar todos los sub-palíndromos en $O(N)$

Enunciado

Se da un string $s$ de longitud $n$ . Encontrar todos los pares $(i, j)$ tales que la subcadena $s[i\dots j]$ es un palíndromo. Un string $t$ es un palíndromo cuando $t = t_{rev}$ ( $t_{rev}$ es el string invertido de $t$ ).

Enunciado más preciso

En el peor caso un string puede tener hasta $O(n^2)$ subcadenas palindrómicas, y a primera vista parece que no hay un algoritmo lineal para este problema.

Pero la información sobre los palíndromos se puede guardar de forma compacta: para cada posición $i$ encontraremos el número de palíndromos no vacíos centrados en esa posición.

Los palíndromos con un centro común forman una cadena contigua: es decir, si tenemos un palíndromo de longitud $l$ centrado en $i$ , también tenemos palíndromos de longitudes $l-2$ , $l-4$ y así sucesivamente, también centrados en $i$ . Por lo tanto, recolectaremos la información de todas las subcadenas palindrómicas de esta manera.

Los palíndromos de longitud impar y par se contabilizan por separado como $d_{odd}[i]$ y $d_{even}[i]$ . Para los palíndromos de longitud par asumimos que están centrados en la posición $i$ si sus dos caracteres centrales son $s[i]$ y $s[i-1]$ .

Por ejemplo, el string $s = abababc$ tiene tres palíndromos de longitud impar con centros en la posición $s[3] = b$ , es decir, $d_{odd}[3] = 3$ :

$a\ \overbrace{b\ a\ \underbrace{b}$

Y el string $s = cbaabd$ tiene dos palíndromos de longitud par con centros en la posición $s[3] = a$ , es decir, $d_{even}[3] = 2$ :

$c\ \overbrace{b\ a\ \underbrace{a}$

Es un hecho sorprendente que existe un algoritmo, suficientemente simple, que calcula estos “arreglos de palindromicidad” $d_{odd}[]$ y $d_{even}[]$ en tiempo lineal. El algoritmo se describe en este artículo.

Solución

En general, este problema tiene muchas soluciones: con hashing de strings se puede resolver en $O(n\cdot \log n)$ , y con árboles de sufijos y LCA rápido este problema se puede resolver en $O(n)$ .

Pero el método descrito aquí es suficientemente más simple y tiene una constante oculta menor en complejidad temporal y de memoria. Este algoritmo fue descubierto por Glenn K. Manacher en 1975.

Otra forma moderna de resolver este problema y de tratar con palíndromos en general es mediante el llamado árbol palindrómico, o eertree.

Algoritmo trivial

Para evitar ambigüedades en la descripción posterior denotamos qué es el “algoritmo trivial”.

Es el algoritmo que hace lo siguiente. Para cada posición de centro $i$ intenta aumentar la respuesta en uno mientras sea posible, comparando un par de caracteres correspondientes cada vez.

Tal algoritmo es lento: solo puede calcular la respuesta en $O(n^2)$ .

La implementación del algoritmo trivial es:


vector<int> manacher_odd_trivial(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    for(int i = 1; i <= n; i++) {
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Se usaron los caracteres terminales $ y ^ para evitar tratar los extremos del string por separado.

Algoritmo de Manacher

Describimos el algoritmo para encontrar todos los sub-palíndromos de longitud impar, es decir, para calcular $d_{odd}[]$ .

Para un cálculo rápido mantendremos los bordes exclusivos $(l, r)$ del (sub-)palíndromo más a la derecha encontrado (es decir, el (sub-)palíndromo más a la derecha actual es $s[l+1] s[l+2] \dots s[r-1]$ ). Inicialmente ponemos $l = 0, r = 1$ , lo que corresponde al string vacío.

Así, queremos calcular $d_{odd}[i]$ para el siguiente $i$ , y todos los valores anteriores en $d_{odd}[]$ ya se han calculado. Hacemos lo siguiente:

Si $i$ está fuera del sub-palíndromo actual, es decir, $i \geq r$ , simplemente lanzamos el algoritmo trivial.

Así incrementaremos $d_{odd}[i]$ de forma consecutiva y comprobaremos cada vez si la subcadena más a la derecha actual $[i - d_{odd}[i]\dots i + d_{odd}[i]]$ es un palíndromo. Cuando encontremos el primer desajuste o lleguemos a los bordes de $s$ , nos detendremos. En este caso ya habremos calculado $d_{odd}[i]$ . Después de esto, no debemos olvidar actualizar $(l, r)$ . $r$ debe actualizarse de forma que represente el último índice del sub-palíndromo más a la derecha actual.
Ahora consideremos el caso en que $i \le r$ . Intentaremos extraer alguna información de los valores ya calculados en $d_{odd}[]$ . Así, encontremos la posición “espejo” de $i$ en el sub-palíndromo $(l, r)$ , es decir, obtendremos la posición $j = l + (r - i)$ , y comprobamos el valor de $d_{odd}[j]$ . Como $j$ es la posición simétrica a $i$ respecto de $(l+r)/2$ , casi siempre podemos asignar $d_{odd}[i] = d_{odd}[j]$ . Ilustración de esto (el palíndromo alrededor de $j$ se “copia” de hecho al palíndromo alrededor de $i$ ):

$\ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }$

Pero hay un caso delicado que hay que manejar correctamente: cuando el palíndromo “interno” alcanza los bordes del “externo”, es decir, $j - d_{odd}[j] \le l$ (o, lo que es lo mismo, $i + d_{odd}[j] \ge r$ ). Como la simetría fuera del palíndromo “externo” no está garantizada, asignar simplemente $d_{odd}[i] = d_{odd}[j]$ será incorrecto: no tenemos datos suficientes para afirmar que el palíndromo en la posición $i$ tiene la misma longitud.

En realidad, debemos restringir por ahora la longitud de nuestro palíndromo, es decir, asignar $d_{odd}[i] = r - i$ , para manejar correctamente esas situaciones. Después de esto ejecutaremos el algoritmo trivial, que intentará aumentar $d_{odd}[i]$ mientras sea posible.

Ilustración de este caso (el palíndromo con centro $j$ se restringe para caber en el palíndromo “externo”):

$\ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }$

En la ilustración se muestra que el palíndromo con centro $j$ podría ser más grande y salir del palíndromo “externo”, pero, con $i$ como centro, solo podemos usar la parte que cabe por completo en el palíndromo “externo”. Pero la respuesta para la posición $i$ ( $d_{odd}[i]$ ) puede ser mucho mayor que esta parte, así que a continuación ejecutaremos nuestro algoritmo trivial, que intentará hacerlo crecer fuera de nuestro palíndromo “externo”, es decir, hacia la región “try moving here”.

De nuevo, no debemos olvidar actualizar los valores $(l, r)$ después de calcular cada $d_{odd}[i]$ .

Complejidad del algoritmo de Manacher

A primera vista no es obvio que este algoritmo tenga complejidad lineal, porque a menudo ejecutamos el algoritmo naive al buscar la respuesta para una posición particular.

Sin embargo, un análisis más cuidadoso muestra que el algoritmo es lineal. De hecho, el algoritmo de construcción de la función Z, que se parece a este algoritmo, también trabaja en tiempo lineal.

Podemos notar que cada iteración del algoritmo trivial incrementa $r$ en uno. Además $r$ no puede disminuir durante el algoritmo. Así, el algoritmo trivial hará $O(n)$ iteraciones en total.

Las demás partes del algoritmo de Manacher trabajan obviamente en tiempo lineal. Así, obtenemos complejidad $O(n)$ .

Implementación del algoritmo de Manacher

Para calcular $d_{odd}[]$ , obtenemos el siguiente código. Cosas a notar:

$i$ es el índice de la letra central del palíndromo actual.
Si $i$ supera $r$ , $d_{odd}[i]$ se inicializa en 0.
Si $i$ no supera $r$ , $d_{odd}[i]$ se inicializa o bien con $d_{odd}[j]$ , donde $j$ es la posición espejo de $i$ en $(l,r)$ , o bien $d_{odd}[i]$ se restringe al tamaño del palíndromo “externo”.
El bucle while denota el algoritmo trivial. Lo lanzamos independientemente del valor de $k$ .
Si el tamaño del palíndromo centrado en $i$ es $x$ , entonces $d_{odd}[i]$ almacena $\frac{x+1}{2}$ .


vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        if(i <= r) {
            p[i] = min(r - i, p[l + (r - i)]);
        }
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Trabajar con paridades

Aunque es posible implementar el algoritmo de Manacher para longitudes impares y pares por separado, la implementación de la versión para longitudes pares a menudo se considera más difícil, porque es menos natural y fácilmente conduce a errores por uno.

Para mitigar esto, es posible reducir todo el problema al caso en que solo tratamos palíndromos de longitud impar. Para ello, podemos poner un carácter adicional # entre cada letra del string y también al principio y al final del string:

$abcbcba \to #a#b#c#b#c#b#a#,$

$d = [1,2,1,2,1,4,1,8,1,4,1,2,1,2,1].$

Como se puede ver, $d[2i]=2 d_{even}[i]+1$ y $d[2i+1]=2 d_{odd}[i]$ , donde $d$ denota el arreglo de Manacher para palíndromos de longitud impar en el string unido con #, mientras que $d_{odd}$ y $d_{even}$ corresponden a los arreglos definidos arriba en el string inicial.

En efecto, los caracteres # no afectan a los palíndromos de longitud impar, que siguen centrados en los caracteres del string inicial, pero ahora los palíndromos de longitud par del string inicial son palíndromos de longitud impar del nuevo string centrados en caracteres #.

Nótese que $d[2i]$ y $d[2i+1]$ son esencialmente las longitudes incrementadas en $1$ de los palíndromos más grandes de longitud par e impar centrados en $i$ , respectivamente.

La reducción se implementa de la siguiente manera:


vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

Por simplicidad, se omite partir el arreglo en $d_{odd}$ y $d_{even}$ así como su cálculo explícito.

Algoritmo de Manacher - Encontrar todos los sub-palíndromos en O(N)O(N)O(N)