×

Strings and Queries Help

 0 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 :) asked 02 Jul '18, 13:54 614●1●9 accept rate: 12% 1 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] (02 Jul '18, 14:00) 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? (02 Jul '18, 15:05) 1 It magically works now!! (02 Jul '18, 15:14) Thanks Vivek for suggesting alternate approach, but can you please point out where I am going wrong in Hashing? (02 Jul '18, 15:34) hashing does have countercases where it fails(collisions) :) (02 Jul '18, 16:36) But I don't think hashing can have collisions here as $4^{30}$ fits in long long( around $1.4 * 10^{18}$ ). (02 Jul '18, 18:01) 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 (02 Jul '18, 23:50) Only 'a', 'b' and 'c' are allowed as letters :) (03 Jul '18, 14:11) OOh sorry!! I didnt read the question properly :( (03 Jul '18, 14:21) showing 5 of 9 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,726
×655
×342

question asked: 02 Jul '18, 13:54

question was seen: 160 times

last updated: 05 Jul '18, 12:34