OLYMPIADS IN INFORMATICS, 2013, Vol. 7, 90-100
© Institute of Mathematics and Informatics,

ISSN 1822-7732

Where to Use and How not to Use Polynomial String Hashing


Faculty of Mathematics, Informatics and Mechanics, University of Warsaw Banacha 2, 02-097 Warsaw, Poland E-mail: {pachocki,jrad}@mimuw.edu.pl


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.


programming contests, hashing on strings, task evaluation

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe

Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2013