Number of individual palindrome substrings

Question

Given the string, I know how to find the number of palindrome substrings in linear time using the Manacher algorithm. But now I need to find the number of individual / unique palindrome substrings. Now this can lead to the O (n + n ^ 2) algorithm - one “n” for finding all such substrings, and n ^ 2 for comparing each of these substrings with those already found to check if it is unique.

I am sure there is an algorithm with better complexity. I was thinking about maybe trying my luck with suffix trees? Is there an algorithm with better time complexity?

Answer 1

I would just put the substrings that you found in the hash table to prevent the same results from repeating at the same time.

The hash table access time is O (1).

Answer 2

2015 , S. , eertree ( ), . , , , -. . : https://arxiv.org/pdf/1506.04862.pdf