首页 / 软件开发 / 数据结构与算法 / UVa 188：Perfect Hash

UVa 188：Perfect Hash2014-10-09 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=124

类型： 哈希

原题：

Perfect Software, Inc. has obtained a government contract to examine text flowing through a high-speed network for the occurrence of certain words. Your boss, Wally Perfect, has designed a parallel processing system which checks each word against a group of small perfect hash tables.

A perfect hash function maps its input directly to a fully occupied table. Your job is to construct the perfect hash functions from the lists of words in each table. The hash function is of the form

, where C is a positive integer you are to discover, w is an integer representation of an input word, and n is the length of the table. C must be as small as possible. Note that

is the floor function and that for some real number R is the largest integer that is .

Here are Wally"s notes on the subject:

Let

consist of positive integers

. The problem is to find the smallest positive integer C such that

for all

.

C must be a multiple of at least one element of W.

If some

for all

,

then the next largest C that could resolve the conflict is at least

Since all such conflicts must be resolved, it is advantageous to choose the largest candidate from among the conflicts as the next C to test.

You are to convert each word to a number by processing each letter from left to right. Consider `a" to be 1, `b" to be 2,

, `z" to be 26. Use 5 bits for each letter （shift left by 5 or multiply by 32）. Thus `a" = 1, `bz" =

.