Valour's blog

Palindromic Queries
By Valour, 7 years ago, In English

Can someone please help with this problem.

Given a string (s) and some queries where each query is of the form [l, r] we need to find the number of palindromic substrings, where the length of each substring lies in between [l, r].

Constraints
1 <= |S| <= 100000
1 <= |q| <= 100000
1 <= l < r <= |S|

Sample Case:
s = "zz"
q = 1
[l, r] = [1, 2]

For this, the answer must be 3. 'z', 'z', 'zz' are the three substrings which are palindrome and their length in between [1, 2].

The substrings to be considered may not be distinct, i.e if s = "zzz" then "zz" is to be considered twice.

Thanks in Advance!

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I think it can be solved by algorithm "mannaker"!

But also by DP here

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

    Hello! I think the DP solution you provided might not be possible due to the constraints.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

consider each index of your string as a center of palindrome and do a binary search on maximum length string possible using this point as a center. all lengths smaller than that are also possible.You can compute prefix and suffix hash and just see if they are same or not for the length calculation part which can be done in O(1) with O(n) precomputation so your overall ur complexity will be nlogn and for updating lengths you can use bit.and when ur done with this precomputation its just a range query in ur bit

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

I think this can be solved using Manacher's algorithm and prefix sums.

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

    Hello!

    Thanks for your response!

    Can you please elaborate a bit more how can I apply manacher. I tried using it but I am unable to cover the case that "substrings considered may not be distinct". Since manacher uses the results of already processed string.

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

      Manacher's algorithm tells you the length of the longest palindrome substring for every center. So if maximum length palindrome has length x, than we can also make palindromes with length x - 2k (where x - 2k > 0). And using this we can maintain two prefix sums — one for odd lengths and one for even lengths. When we need to answer query we just get sum of both prefix sums in appropriate range.

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

        Thanks! for your help Sir :)
        Have a good day!

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

    will you please provide your code, for the above problem.

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it -12 Vote: I do not like it

Upd: Doesn't work as karanbatra explains.

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

    constraints on the string length in this question is 100000, so O(|S|2) won't work.

    → Reply
»
7 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Hint:The number of distinct palindromes in a string of length n can't exceed n

→ Reply