AzorAhai's blog

help with this interesting gym problem

By AzorAhai, history, 8 years ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AzorAhai (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this can be solved with Suffix Automata. A similar problem where you have to count substrings of any kind can be solved using this. Not sure about palindromic substring counting though.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You can modify Manacher's algorithm + DP ,and solve it in O(N). I don't know how this works but here you go :

If you only need a hint, don't open this link! http://stackoverflow.com/questions/19801081/find-all-substrings-that-are-palindromes

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks MedoN11 but the solution in the link solve the problem of counting palindromic substrings in the whole string but my problem is how to count them efficiently in some given range .. do you have an idea how to do so

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you could do manacher to get the palindromes and then do mo's algorithm on queries, it will be

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How would I updadte the count when extending/shrinking the current intervall?

    → Reply