Strings and Queries Help

general
, ,
1

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 :slight_smile:

2

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

edit:sorry not stack,dp

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

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

1 Like
3

I tried with what you said… Picked code from GFG xD. But it still shows WA :frowning:
Here’s the link : (https://ideone.com/mipoDA)
Am I doing something wrong still?

4

It magically works now!!

1 Like
5

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

6

hashing does have countercases where it fails(collisions) :slight_smile:

7

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

8

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

One countercase(collision) is:

string gd,ce

both strings have hash value 23

7+44=3+45=23

9

Only ‘a’, ‘b’ and ‘c’ are allowed as letters :slight_smile:

10

OOh sorry!! I didnt read the question properly :frowning: