O algoritmo de manacher encontra todos os palíndromos de uma string em 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