Question

For any given string x=x1x2x3⋯xm, a hash function is defined below as:

(This is the entire question, i cannot update it because this is it in its entirety)

h(x)=[c(x1)+c(x2)q+c(x3)q^2+⋯+c(xm)q^m-1 mod P

Here, both  and P are given small prime numbers, and denote the ASCII integer of the letter xi,1≤i≤m. For any string y=y1y2⋯yn, please show that if the hash value of the hash value yiyi+1⋯yi+k is known, then the hash value of yi+1yi+2⋯yi+k+1 can be computed in constant time. Please type answer if you can.

Answer 1

Let Hash value for  yiyi+1⋯yi+k = h1(y)=[c(y1)+c(y1+2)q+c(y1+3)q^2+⋯+c(y1+k)q^m-1] mod P

Let time taken to calculate this hash value be t, and since we already have this value, the time taken to calculate it again will be O(1).

Now, Hash value for yiyi+1⋯yi+k.yi+k+1 = h2(y)=[c(y1)+c(y1+2)q+c(y1+3)q^2+⋯+c(y1+k)q^m-1 + c(y1+k+1)q^m] mod P

By the property of mod, this can be written as

h2(y) = [c(y1)+c(y1+2)q+c(y1+3)q^2+⋯+c(y1+k)q^m-1] mod P + c(y1+k+1)q^m mod P

h2(y)=h1(y)+c(y1+k+1)q^m mod P

Since, c(y1+k+1)q^m mod P is a simple expression, time taken to calculate is one unit.

We already have the value of h1(y), so no need to calculate it again.

now, h2(y) is a simple addition operation and takes one unit of time.

So total time taken = 1 unit + 1 unit = 2 units

2 units is constant time. Hence proved.