saba_tavdgiridze's blog

By saba_tavdgiridze, history, 5 years ago,

Hi , I was trying to solve this problem , which is about finding number of unique palindromic substrings in string of size n . As n can be large(10^5) ,only feasible is nlogn algorithm for this problem.Can you help me ? ( I was trying to solve with suffix array but don't succeed )

• -5

 » 5 years ago, # |   0 The problem is just a simple application of eertree (palindromic tree).
•  » » 5 years ago, # ^ |   -8 I have known about this algorithm , but problem is one should't study every(and not so useful ) data structure for solving problems . It's better to know few and know it well.
•  » » » 5 years ago, # ^ |   0 You don't need palindromic tree. This problem existed before palindromic trees became well-known. You only need to be familiar with Manacher's algorithm and maybe not even that, if O(N log N) passes .
•  » » » » 5 years ago, # ^ |   0 how?
•  » » » » » 5 years ago, # ^ |   0 Let's call the array that you're supposed to output V. Think about how much V[i] can differ from V[i — 1] in general.
 » 5 years ago, # |   0 There are my very old code for this problem, that using hashes: http://pastebin.com/SZmQFEL2