Rolling hash

Questions 1 to 5 of 6

1. 1. After the RollingHash constructor below has built the prefix and power lists for a string of length n, what does one call to hash(start, end) cost as the piece gets longer? ``python class RollingHash: def __init__(self, text, base, mod): self.mod = mod self.prefix = [0] * (len(text) + 1) self.power = [1] * (len(text) + 1) for i, ch in enumerate(text): self.prefix[i + 1] = (self.prefix[i] * base + ord(ch)) % mod self.power[i + 1] = (self.power[i] * base) % mod def hash(self, start, end): return (self.prefix[end] - self.prefix[start] * self.power[end - start]) % self.mod ``

   It grows with the piece length, about k steps for a piece of length kIt grows with n, the length of the whole stringIt stays the same, a fixed number of arithmetic steps whatever the piece lengthIt is zero, because the answer is read from a table
2. 2. What does building the prefix and power lists in the constructor cost, for a string of length n? (O(n) means the work grows in step with n.)

   O(n), one pass over the stringO(n squared), because each prefix is rebuilt from the startO(1), because the lists are filled only when they are readO(log n), because the length doubles at each step
3. 3. A common check first compares the two hashes of two pieces, and then compares their characters. Why is the character check still needed?

   Because computing a hash is slower than comparing charactersBecause the hash only works for pieces of length oneBecause a slice comparison is needed to compute the hash in the first placeBecause two different pieces can share a hash, so a matching hash only means the pieces are probably equal
4. 4. The hash method ends with % self.mod, and the value before that step can be negative. What does (-7) % 5 give in Python?

   -2, because the remainder keeps the sign of -7-7, because a negative number is not divided3, because Python's % always gives a result from 0 up to the divisor minus 12, because -7 rounds up to -5 first
5. 5. Using the RollingHash class from the first question, what does this code print? ``python rh = RollingHash('abcab', 10, 1_000_000_007) print(rh.hash(3, 5)) print(rh.hash(0, 3)) print(rh.hash(3, 5) == rh.hash(0, 2)) ``

   1068, 10779, False1068, 10779, True97, 979, True1068, 9979, True