How can we perform segment queries with Palindromic Tree?

Revision en1, by duckladydinh, 2018-11-13 13:48:46

Hi everyone,

I am learning this relatively new data structure with a Kattis problem called Palindromes. In this problem, we are given a string and multiple [l, r] segments and must find the number of palindromic substrings in each segment. The number of queries and length of the string are all 10^5. My question is: Is it possible to achieve this with Palindromic Tree and if yes, how can we do that?

I am not absolutely sure if this DS can handle such problems, but at least, I know that for [1, r] segments, it is possible, Is this variant possible? If it is possible, please give me your guidance.

Thank you very much :). Happy Coding


  Rev. Lang. By When Δ Comment
en1 English duckladydinh 2018-11-13 13:48:46 706 Initial revision (published)