ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1713. Key Substrings

Hash is not working. HELP!
Posted by Pavel Kovalenko 2 May 2010 05:46
If i use hash-table, i get WA. Because due to the small MOD ~10^6, i get probably a coincidence of some hashes.
(I used the degree = 31 and tried modules 1000003,... etc.)

If i use simply linear hash (in common vector) and sorting i get TL.

If i keep hash of each string in separate vectors, and then use a binary search, then again i get TL.

Re: Hash is not working. HELP!
Posted by Igor9669 2 May 2010 16:38
I got a lot of TLE while using vector... then I changed it to simple array and got Ac.
Re: Hash is not working. HELP!
Posted by ASK 11 Mar 2018 02:44
Hash works just fine (h = h*P + n, where h is size_t, P is some prime, and n is the next char), but you need to keep the loop order: for each length first go thru all substrings to fill unordered_map<substring,int> and then for each non-answered command and all its substrings of the current length check if they have been seen only in this command.

Note that the hash can be rolled from one substring of fixed length to the next and it seems equal_to can always return true (tried for P=127).