I was trying this problem from Gym Contest. I don’t know why I am getting WA on Test 2. Here’s my code : Link.

I have used Hashing for checking number of palindromes and then Segment Tree to find the index for each query. Can anyone point out whats wrong in my code or give an alternate solution.

Thanks

# Strings and Queries Help

**dishant_18**#1

why hashing?since length<30,u could just use an O(length^2) algorithm(stack)

edit:sorry not stack,dp

dp*[j] denotes if substring s[i:j] is a palindrome

dp*[j]=true if dp[i+1][[j-1] is true and s*==s[j]

**dishant_18**#3

I tried with what you said… Picked code from GFG xD. But it still shows WA

Here’s the link : (https://ideone.com/mipoDA)

Am I doing something wrong still?

**dishant_18**#5

Thanks Vivek for suggesting alternate approach, but can you please point out where I am going wrong in Hashing?

**dishant_18**#7

But I don’t think hashing can have collisions here as 4^{30} fits in long long( around 1.4 * 10^{18} ).

Ur hash function is sum(4^i*(s*-‘a’+1)) if i am not wrong

One countercase(collision) is:

string gd,ce

both strings have hash value 23

7+4*4=3+4*5=23