help with this interesting gym problem

Правка en2, от 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.

Теги palindroms, strings, data structures

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AzorAhai 2016-04-30 21:23:33 9 Tiny change: 'th < 10^5 and want' -> 'th < 10^5 is given and want'
en1 Английский AzorAhai 2016-04-30 21:22:04 504 Initial revision (published)