Suppose we want to determine if the string s=s1s2...sk is a substring much larger string a1a2...an. One approach is to compute h(s) with some hash function h. . Then, for each i = 1; 2,....,n-k+1 compute h(aiai+1...ai+k-1). If this value is identical to h(s), then compare this string with s, and return true if strings are identical. Otherwise proceed to next substring. Argue that the running time of this algorithm is O(kn). Prove that, if we assume the hash function is h(x0 ....x1)= E(l to i=0) xl-1 37^i. Then the running time can be reduced to O(n). Hint: argue that h(ai+1ai+2.... ai+k) can be computed in theta(1) steps assuming h(aiai+1...ai+k-1) has been computed.