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!
I think it can be solved by algorithm "mannaker"!
But also by DP here
Hello! I think the DP solution you provided might not be possible due to the constraints.
Oh sorry, I didn't notice the constraints.
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
I think this can be solved using Manacher's algorithm and prefix sums.
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.
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.
Thanks! for your help Sir :)
Have a good day!
will you please provide your code, for the above problem.
Upd: Doesn't work as karanbatra explains.
constraints on the string length in this question is 100000, so O(|S|2) won't work.
Hint:The number of distinct palindromes in a string of length n can't exceed n