<p>As of 2015, there is a linear time algorithm for computing the <em>number of distinct palindromic substrings</em> of a given string S. You can use a data structure known as an <a href="https://arxiv.org/pdf/1506.04862.pdf" rel="nofollow noreferrer">eertree (or palindromic tree)</a>, as described in the linked paper. The idea is fairly complicated, but the premise is to build a trie of palindromes, and augment it with longest proper palindromic suffixes in a similar manner to the failure function of the <a href="https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm" rel="nofollow noreferrer">Aho-Corasick Algorithm</a>. See the original paper for more details: <a href="https://arxiv.org/pdf/1506.04862.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1506.04862.pdf</a></p>
Number of distinct palindromic substrings
<p>Given a string, I know how to find the <em>number of palindromic substrings</em> in linear time using Manacher's algorithm. But now I need to find the number of <em>distinct/unique</em> palindromic substrings. Now, this might lead to an O(n + n^2) algorithm - one 'n' for finding all such substrings, and n^2 for comparing each of these substrings with the ones already found, to check if it is unique.</p>

<p>I am sure there is an algorithm with better complexity. I was thinking of maybe trying my luck with suffix trees? Is there an algorithm with better time complexity?</p>