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

Jakub PACHOCKI, Jakub RADOSZEWSKI

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

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.

Keywords:

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