Hashing and Aho-Corasick

Questions 1 to 5 of 8

1. 1. Why is hashing with natural unsigned long long overflow (modulus 2^64) unsafe, even though it is fast?

   Overflow makes unsigned 64-bit arithmetic too slow to use in a contest.The wrap-around is not random, so structured strings such as Thue-Morse words can collide, and random tests may not show it.Overflow turns 2^64 into a prime, which breaks the modulus.It works only for alphabets with more than 26 letters.
2. 2. An AI wrote this hash: the base is 131 and fixed, the modulus is 2^61 - 1, and each product is computed as a * b % MOD in plain unsigned 64-bit arithmetic. It passes a random test. What is the main risk?

   No risk: the modulus is prime, so products stay small enough.The only risk is speed, since % is slow.Two faults: a base copied from a tutorial can be targeted by test data, and a product near 2^122 wraps in 64 bits, so equal substrings can get unequal hashes.A passing random test proves there is no collision, so the code is correct.
3. 3. Use base 10, no modulus, and the letter codes a = 1, b = 2, c = 3. The string cab reads as 312. What is 312 modulo 7?

   Type a number.

4. 4. Which practices lower the risk of a wrong hash comparison? Select all that apply.

   Pick every answer that is true.

   Draw the base at run time from a range well above the character codes.Use a prime modulus such as 2^61 - 1 with a 128-bit product.Hard-code base 131 copied from a blog post, so results are reproducible.Compare two substrings only when their lengths are equal.Use base 1, so the hash is the simplest possible sum.
5. 5. In the ushers example, the reverse pass adds the count of she into he. Which reason is correct?

   he comes before she in the input, so its count is copied from the first pattern.The reverse pass adds the count of she into he because she is longer, so the count flows to the shorter word.Failure links point to longer nodes, so the pass moves the counts forward through the text.he is a proper suffix of she, and the failure link of she is he, so every occurrence of she also ends with an occurrence of he.