Understanding Rabin-Karp algorithm with modulo arithmetic

First, what is the hash function used to calculate values for character sequences? Second, isn’t it time-consuming to hash every one of the M-character sequences in the text body?

Consider an M-character sequence as an M-digit number in base b, where b is the number of letters in the alphabet. The text subsequence t[i .. i+M-1] is mapped to the number:

x(i) = t[i]*b^M-1+ t[i+1]*b^M-2+...+ t[i+M-1]

Furthermore, given x(i) we can compute x(i+1) for the next subsequence t[i+1 .. i+M] in constant time, as follows:

x(i+1) = t[i+1]∗b^M-1+ t[i+2]*b^M-2+...+ t[i+M]

x(i+1) =  x(i)*b (Shift left one digit)
         - t[i]*b^M (Subtract leftmost digit)
         + t[i+M] Add new rightmost digit

In this way, we never explicitly compute a new value. We simply adjust the existing value as we move over one character.

If M is large, then the resulting value (b^M) will be enormous. For this reason, we hash the value by taking it mod a prime number q.

The mod function is particularly useful in this case due to several of its inherent properties:

[(x mod q) + (y mod q)] mod q = (x+y) mod q
(x mod q) mod q = x mod q

For these reasons:

h(i) = ((t[i]* b^M-1mod q) +(t[i+1]* b^M-2mod q) +... +(t[i+M-1] mod q)) mod q
h(i+1) =( h(i)* b mod q (Shift left one digit)
        -t[i]* b^M mod q (Subtract leftmost digit)
        +t[i+M] mod q ) (Add new rightmost digit)
        mod q

We can determine the hash value using this formula:

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......