Algoritmo de Manacher - Encontrando todos os sub-palíndromos em $O(N)$

Dada uma string $s$ de comprimento $n$. Encontre todos os pares $(i, j)$ de modo que a substring $s[i\dots j]$ seja um palíndromo. A string $t$ é um palíndromo quando $t = t_{rev}$ ($t_{rev}$ é uma string invertida para $t$).

Descrição

É claro que, no pior dos casos, podemos ter $O(n^2)$ strings palíndromos, e, à primeira vista, parece que não há algoritmo linear para esse problema.

Mas as informações sobre os palíndromos podem ser mantidas em uma forma mais comprimida: para cada posição $i = 0\dots n-1$ encontraremos os valores $d_1[i]$ e $d_2[i]$, indicando o número de palíndromos de acordo com comprimentos ímpares e pares com centros na posição $i$.

Por exemplo, a string $s = abababc$ tem três palíndromos com comprimento ímpar, com centros na posição $s[3] = b$, i. e. $d_1[3] = 3$:

$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{d_1[3]=3} c$

E a string $s = cbaabd$ tem dois palíndromos de comprimento par com centros na posição $s[3] = a$, ou seja, $d_2[3] = 2$:

$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{d_2[3]=2} d$

Portanto, a ideia é que, se tivermos um sub-palíndromo com comprimento $l$ com centro em alguma posição $i$, ambém teremos sub-palíndromos com comprimentos $l-2$, $l-4$ etc. com centros em $i$. Então, essas duas arrays $d_1[i]$ e $d_2[i]$ são suficientes para manter as informações sobre todos os sub-palíndromos da string.

É um fato surpreendente que exista um algoritmo, bastante simples, que calcule essas "arrays de palíndromes" $d_1[]$ e $d_2[]$ em tempo linear. O algoritmo é descrito neste artigo.

Solução

Em geral, esse problema tem muitas soluções: com String Hashing ele pode ser resolvido em $O(n\cdot \log n)$, e com Árvore de Sufixos e LCA rápido, esse problema pode ser resolvido em $O(n)$.

Mas o método descrito aqui é suficientemente simples e tem uma menor constante oculta na complexidade do tempo e da memória. Este algoritmo foi descoberto por Glenn K. Manacher em 1975.

Algoritmo trivial

Para evitar ambiguidades na descrição adicional, denotamos o que é o "algoritmo trivial".

É o algoritmo que faz o seguinte. Para cada posição central $i$ ele tenta aumentar a resposta em um até que seja possível, comparando um par de caracteres correspondentes a cada vez.

Esse algoritmo é lento, só pode calcular a resposta em $O(n^2)$.

A implementação do algoritmo trivial é:

vector<int> d1(n),  d2(n);
for (int i = 0; i < n; i++) {
    d1[i] = 1;
    while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
        d1[i]++;
    }

    d2[i] = 0;
    while (0 <= i - d2[i] - 1 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]) {
        d2[i]++;
    }
}

Algoritmo de Manacher

Nós descrevemos o algoritmo para encontrar todos os sub-palíndromos com comprimento ímpar, ou seja, para calcular $d_1[]$; a solução para todos os sub-palíndromos com comprimento par (isto é, calcular a array $d_2[]$) será uma pequena modificação para este aqui.

Para um cálculo rápido, manteremos as extremidades $(l, r)$ do sub-palíndromo encontrado mais à direita (ou seja, o palíndromo com o máximo $r$). Inicialmente assumimos $l = 0, r = -1$.

Portanto, queremos calcular $d_1[i]$ para os próximos $i$, e todos os valores anteriores em $d_1[]$ já foram calculados. Faremos o seguinte:

No final, é necessário lembrar que não devemos esquecer de atualizar os valores $(l, r)$ após calcular cada $d_1[i]$.

Também repetiremos que o algoritmo foi descrito para calcular o array para palíndromos ímpares $d_1[]$, o algoritmo é semelhante para o de array de palíndromos pares $d_2[]$.

Complexidade

À primeira vista, não é óbvio que esse algoritmo tenha complexidade de tempo linear, porque geralmente executamos o algoritmo trivial enquanto procuramos a resposta para uma posição específica.

Porém, análises mais cuidadosas mostram que o algoritmo é linear no entanto. Precisamos mencionar a construção do algoritmo da função-Z que se parece com esse algoritmo e também funciona em tempo linear.

Na verdade, podemos notar que cada iteração de algoritmo trivial aumenta $r$ em um. Além disso, $r$ ão pode ser diminuído durante o algoritmo. Portanto, o algoritmo trivial fará $O(n)$ iterações no total.

Além disso, outras partes do algoritmo de Manacher funcionam em tempo linear. Assim, obtemos uma complexidade de tempo de $O(n)$.

Implementação do algoritmo de Manacher

Para calcular $d_1[]$, obtemos o seguinte código:

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
        k++;
    }
    d1[i] = k--;
    if (i + k > r) {
        l = i - k;
        r = i + k;
    }
}

Para calcular $d_2[]$, o código parece semelhante, mas com pequenas alterações nas expressões aritméticas:

vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
        k++;
    }
    d2[i] = k--;
    if (i + k > r) {
        l = i - k - 1;
        r = i + k ;
    }
}

Problemas

UVA #11475 "Extend to Palindrome"