Before a hash table can index anything it needs a number. The pre-hash of a string treats its characters as the digits of a number in base base:
\mathrm{ph}(s) \;=\; \left(\sum_{i=0}^{|s|-1} \mathrm{ord}(s_i)\cdot \mathrm{base}^{\,i}\right) \bmod 2^{\mathrm{width}}
Write prehash(word, base, width) returning that value. The empty string pre-hashes to 0.
Examples
Input: word = "ab", base = 31, width = 8
Output: 63
Explanation: 97 + 98*31 = 3135, and 3135 mod 256 = 63.
Input: word = "", base = 31, width = 8
Output: 0
Constraints
0 <= len(word) <= 10**5, printable characters1 <= base <= 10**6,1 <= width <= 64- Never build
base ** ifor a largei; keep the running value reduced.
Goals
- Map a string to a non-negative integer before any table index is computed
- Evaluate a polynomial with Horner's rule so the running value stays small
- Reduce at every step instead of once at the end