Consider a hash function that computes the hash value of a string in linear time. You are provided with the following description of the hash function:
It takes a string as input.
It iterates through the string from left to right.
In step , it calculates the hash value of the th prefix, i.e. the substring from the first character to the th one. In other words, if the string is , at the th step it computes .
It returns the list of these hash values in the same order they appear concatenated as a string.
Is it a good hash function? If not, which property is missing here?
Tip: Think about how the runtime of the described hash function might be affected by the size of the input string. Does the runtime increase proportionally with the length of the input?