We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Where to Use and How not to Use Polynomial String Hashing.
- Authors
PACHOCKI, Jakub; RADOSZEWSKI, Jakub
- Abstract
We discuss the usefulness of polynomial string hashing in programming competition tasks. We show why several common choices of parameters of a hash function can easily lead to a large number of collisions. We particularly concentrate on the case of hashing modulo the size of the integer type used for computation of fingerprints, that is, modulo a power of two. We also give examples of tasks in which string hashing yields a solution much simpler than the solutions obtained using other known algorithms and data structures for string processing
- Subjects
HASHING; COMPUTER programming; INTEGER programming; FINGERPRINT databases; ALGORITHMS; WORD processors; CONTESTS
- Publication
Olympiads in Informatics, 2013, Vol 7, p90
- ISSN
1822-7732
- Publication type
Article