help with this interesting gym problem

Revision en2, by AzorAhai, 2016-04-30 21:23:33

Hi guys, I need your help in this problem. it is problem 'K' (subpalindroms) in this contest http://www.codeforces.com/gym/100032/attachments. in the problem a string S with length < 10^5 is given and want us to answer m <3*10^5 queries, each query want us to count the number of palindromic substrings in a given interval. I couldn't find any solution better than O(n^2) although I tried to use hashing and palindromic tree any hint please .. thanks in advance.

Tags palindroms, strings, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AzorAhai 2016-04-30 21:23:33 9 Tiny change: 'th < 10^5 and want' -> 'th < 10^5 is given and want'
en1 English AzorAhai 2016-04-30 21:22:04 504 Initial revision (published)