Rolling hash

Questions 1 to 5 of 6

1. 1. After a PrefixHash is built for a string of n letters, how many steps does one call to get(start, len) take, whatever len is? Do not count a character check.

   O(len), one step for each letter in the substringO(1), a fixed number of stepsO(n), one step for each letter of the whole textO(n log n), because of the binary search
2. 2. How many steps does it take to build the prefix and power arrays for a string of n letters?

   O(1)O(log n)O(n)O(n squared)
3. 3. Why does findAll compare the characters with text.compare after the two numbers match?

   Two different substrings can have the same hash, which is a collisionThe hash can only be computed for windows that end at the last letterstd::string::compare is needed to build the prefix arrayThe power array is only filled for the first half of the text
4. 4. In get, the code is upper + mod_ - removed, with mod_ added before the subtraction. Why?

   To make the hash bigger, so collisions are rarerTo convert the base from 131 to 1000000007To check the index, the way .at() doesUnsigned integers wrap around when a subtraction goes below zero, so adding the modulus first keeps the value positive
5. 5. What does this program print? ``cpp #include <cstdint> #include <iostream> int main() { const uint64_t mod = 11; uint64_t upper = 1068 % mod; uint64_t removed = 97 % mod * 10 % mod; std::cout << (upper + mod - removed) % mod << "\n"; } ``

   981012