Hash is not working. HELP!

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!

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).