CODEWITHSUNDEEP
stringalgorithmsubstringtime-complexitypalindrome
Liam Willis
Liam Willis

Reputation: 681

Number of distinct palindromic substrings

Given a string, I know how to find the number of palindromic substrings in linear time using Manacher's algorithm. But now I need to find the number of distinct/unique 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.

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?

Upvotes: 4

Views: 3858

Answers (2)

Eric Zhang
Eric Zhang

Reputation: 601

As of 2015, there is a linear time algorithm for computing the number of distinct palindromic substrings of a given string S. You can use a data structure known as an eertree (or palindromic tree), 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 Aho-Corasick Algorithm. See the original paper for more details: https://arxiv.org/pdf/1506.04862.pdf

Upvotes: 2

zavg
zavg

Reputation: 11081

I would just put substrings you found into the hash table to prevent holding the same results twice.

The access time to hash table is O(1).

Upvotes: 3

Related Questions