Counting Distinct Palindromic Substrings Given a string $S$, I want to count the number of distinct palindromic substrings of  $S$. I know the basic $o(n^2)$ approach to do so. But I want to find a better approach for strings that can be very large (of the order of $10^5$).
So I want a more efficient algorithm.
Example: 
Say $S=xyx$, then the palindromic counter must return $3$ as answer, as S has three palindromic substrings: $\{x,xyx,y\}$.
 A: You can get a table of the largest palindrome centered at each position using Manacher's algorithm in $O(n)$ time.  Then create a set of palindromes (e.g. using a min heap), initially empty.  Iterate over the table, adding the longest palindrome centered at each position to the set.  When adding a palindrome to the set, if successful, remove the first and last characters and repeat until the string is empty or a previously-added palindrome is found.
This runs in time $O(n \log p)$, where $p$ is the palindrome count.
A: Every 1-character substring is a palindrome -- as the OP already pointed out in the example. Also, every repeated character is a length-2 palindrome, e.g. $xx$ in $axxb$.
Use the set of 1-character and 2-character palindromes as your initial set. Then, for each palindrome in the set, try to extend it by 1 character left and 1 character right and check if that is still a palindrome. This happens if the characters to the left and right of an existing palindrome are equal. If they are equal, add the new palindrome to the set and try to add 2 more characters. If the step did not form a new palindrome, stop and try the next element in the existing set.
In the worst case this is still $o(n^2)$, which would happen, for example, if the string is a single character repeated $n$ times. In the best case this is $o(n)$ since palindromes are quite rare and most attempts at extending from a 1 or 2-character palindrome will end after a constant number of steps. The average case performance will depend a lot on the expected density of palindromes in the string.
