Manacher

Manacher

O algoritmo de manacher encontra todos os palíndromos de uma string em $\mathcal{O}(n)$. Para cada centro, ele conta quantos palíndromos de tamanho ímpar e par existem (nos vetores d1 e d2 respectivamente). O método solve computa os palíndromos e retorna o número de substrings palíndromas. O método query retorna se a substring s[i...j] é palíndroma em $\mathcal{O}(1)$.