Dada uma string, eu sei como encontrar onúmero de substrings palindrômicas em tempo linear usando o algoritmo de Manacher. Mas agora preciso encontrar o número dedistinto / único substrings palindrômicos. Agora, isso pode levar a um algoritmo O (n + n ^ 2) - um 'n' para encontrar todas essas substrings, e n ^ 2 para comparar cada uma dessas substrings com as já encontradas, para verificar se é única.

Tenho certeza de que existe um algoritmo com melhor complexidade. Eu estava pensando em talvez tentar a minha sorte com árvores de sufixo? Existe um algoritmo com melhor complexidade de tempo?