|
|
вернуться в форум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.
:( I got a lot of TLE while using vector... then I changed it to simple array and got Ac. 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). |
|
|
