Where to Use and How not to Use Polynomial String Hashing
Jakub Pachocki, Jakub Radoszewski · OLYMPIADS IN INFORMATICS · 2013
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.