Perfect Hash

Perfect Software, Inc. has a government contract to scan text flowing through a high-speed network for certain words. The system checks each word against a group of small perfect hash tables, and your task is to build the perfect hash function for each table.

A perfect hash function maps every input directly into a fully occupied table (no collisions and no empty slots). The hash function has the form $\lfloor C / w \rfloor \bmod n$, where:

• $C$ is a positive integer you must discover,
• $w$ is the integer representation of an input word, and
• $n$ is the length of the table (the number of words in the list).

$C$ must be as small as possible. Here $\lfloor R \rfloor$ is the floor of $R$: the largest integer that is $\le R$.

Finding $C$. Let $W = \lbrace w_1, w_2, \ldots, w_n \rbrace$ be the word values, sorted so that $w_1 < w_2 < \cdots < w_n$. Find the smallest positive integer $C$ such that

$\left\lfloor \frac{C}{w_i} \right\rfloor \bmod n \neq \left\lfloor \frac{C}{w_j} \right\rfloor \bmod n \quad \text{for all } 1 \le i < j \le n.$

The smallest such $C$ is always a multiple of at least one element of $W$.

A useful observation: if $\left\lfloor \frac{C}{w_i} \right\rfloor \bmod n = \left\lfloor \frac{C}{w_j} \right\rfloor \bmod n$ for some pair $i \neq j$ (a collision), then neither of those two floor values can change until $C$ reaches at least

$\min\left( \left( \left\lfloor \frac{C}{w_i} \right\rfloor + 1 \right) \cdot w_i, \; \left( \left\lfloor \frac{C}{w_j} \right\rfloor + 1 \right) \cdot w_j \right),$

so no smaller $C$ can resolve that collision. Because every collision must be resolved, it is efficient to advance $C$ to the largest of these thresholds over all current collisions and test again.

Encoding a word. Convert each word to a number by processing its letters from left to right. Treat 'a' as 1, 'b' as 2, $\ldots$, 'z' as 26, using 5 bits per letter (shift left by 5, i.e. multiply by 32, before adding the next letter). Thus 'a' $= 1$ and 'bz' $= (2 \cdot 32) + 26 = 90$.

The input is a series of word lists, one per line, until end-of-file. Each line has between two and thirteen words, each at most five lowercase letters, separated by one or more spaces. Every line contains at least one single-letter word.

For each word list, print the input line, then on the next line print the value of $C$ for that list's hash function. Print a blank line between the answers for consecutive lists. $C$ always fits in a signed 32-bit integer.