# Understanding Rabin-Karp's rolling hash computation

Possibly related to this. Let $$T$$ be the text and $$n$$ be the length of the pattern. I understand that if substrings of $$T$$ are interpreted as base-$$d$$ numbers where $$d$$ is the alphabet's size, then for all suitable $$k$$: $$T[k+1\text{..}k+n] = (T[k\text{..}k+n−1] − T[k]\cdot d^{n-1})\cdot d + T[k+n]$$ What I don't understand is why: $$T[k+1\text{..}k+n]\pmod{q} = ((T[k\text{..}k+n−1]\pmod{q} − T[k]\cdot h)\cdot d + T[k+n])\pmod{q}$$ where $$h=d^{n-1}\pmod{q}$$. Given the base recurrence above, how do you derive the corresponding modular-arithmetic recurrence? Did I even write it correctly?

#### Two modulo operations

There are two modulo operations for a modulus $$0\not=q\in\Bbb N$$. $$\newcommand{\q}{\!\!\pmod q}$$ $$\newcommand{\Q}{\text{mod}_q}$$.

• Let $$\text{mod}_q:\Bbb Z\to\Bbb Z/q\Bbb Z$$, $$\text{mod}_q(x)=\{\cdots, x-2q,x-q, x, x+q, x+2q, \cdots,\}$$. We also write the last set as $$\bar x_q$$ or $$x\q$$ or, with $$q$$ understood, $$\bar x$$.
• Let $$\%_q: \Bbb Z\to\{0,1,2,\cdots, q-1\}\subset\Bbb Z$$, $$\%_q(x)$$ is the unique number in $$\{0,1,2,\cdots, q-1\}$$ whose difference with $$x$$ is a multiple of $$q$$. We will write $$\%_q(x)$$ also as $$x\%q$$, just as what we do in various programming languages.

Please note these two similar modulo operations are very different!

Any equality of expressions of integers that involve only addition, subtraction, multiplication and exponentiation with positive exponent becomes an equality in $$\Bbb Z/q\Bbb Z$$ when we apply $$\text{mod}_q$$ to every integer except the exponents in the equality.

Since $$\text{mod}_q$$ is so well-behaved, people also write expression like $$5\!\!\pmod7+4$$, or $$T[k\text{..}k+n−1]\q − T[k]⋅h$$. Thinking for a moment, how will you interpret the meaning of $$5\!\!\pmod7+4$$? Is the result an integer or an element in $$\Bbb Z/7\Bbb Z$$? Where does the addition take place?

That ambiguity or sloppiness might be the reason you doubt "did I even write it correctly?"

When we apply $$\text{mod}_q$$ to an equality, we usually write like the following, where $$\!\!\pmod q$$ is just appended to the equality once. $$T[k+1\text{..}k+n] = (T[k\text{..}k+n−1] − T[k]⋅d^{n-1})⋅d + T[k+n]\pmod{q},$$ which is a shorthand for $$\Q(T[k+1\text{..}k+n]) =\Q((T[k\text{..}k+n−1] − T[k]⋅d^{n-1})⋅d + T[k+n])$$

#### The correct equality

Instead of the sloppy one in the question, what you intended to write might be the following equality in $$\Bbb Z$$. $$T[k+1\text{..}k+n]\%q = ((T[k\text{..}k+n−1]\%q − T[k]⋅h)⋅d + T[k+n])\%q\label{***}\tag{***}$$ where $$h:=d^{n-1}\%q$$.

Let us prove it. We know that (as integers) $$T[k+1\text{..}k+n] = (T[k\text{..}k+n−1] − T[k]⋅d^{n-1})⋅d + T[k+n]$$

By definition of $$\%q()$$, we know $$x-x\%q$$ is a multiple of $$q$$ for all $$x$$. In particular, for some integer $$a,b$$, $$T[k\text{..}k+n−1]= T[k\text{..}k+n−1]\%q + q\cdot a$$ $$d^{n-1}= d^{n-1}\%q + q\cdot b$$ So, $$(T[k+1\text{..}k+n])- (T[k\text{..}k+n−1]\%q − T[k]⋅(d^{n-1}\%q))⋅d + T[k+n])=(qa-T[k]\cdot q\cdot b)\cdot d,$$ which is a multiple of $$q$$. Since $$x\%q=y\%q$$ when the difference between $$x$$ and $$y$$ is a multiple or $$q$$ (i.e., when $$x\q=y\q$$), we obtain $$\eqref{***}$$.

People could also interpret the equality in the question as the following equality in $$\Bbb Z/q\Bbb Z$$, $$\Q(T[k+1\text{..}k+n]) = (\Q(T[k\text{..}k+n−1]) − \Q(T[k])⋅h)⋅\Q(d) + \Q(T[k+n])$$ where $$h:=\Q(d^{n−1})$$, or the following equality in $$\Bbb Z$$, $$\overline\%q(\Q(T[k+1\text{..}k+n])) = \overline\%q(\Q((T[k\text{..}k+n−1]) − T[k]\cdot h)\cdot(d) + (T[k+n])))$$ where $$h:=d^{n-1}$$ and $$\overline\%q:\Bbb Z/q\Bbb Z\to\Bbb Z$$, $$\overline\%q(\Q(x))=\%q(x)$$.

#### A defense for sloppiness

There is a reason why people become sloppy when applying $$\Q$$ or $$\%_q$$.

Sloppy-Modulo principle. Fix a modulus $$q$$. Given two expressions, we can replace any integer in either expression by another integer whose difference from it is a multiple of $$q$$ repeatedly any number of times. As long as the last step is applying $$\Q$$ or $$\%_q$$ or $$\overline\%_q$$ to both sides, the two expressions at the end will be equal if they were equal originally.

Although not for all expressions such as the ones that involve division, the principle applies to many situations, endowing you with lots of freedom to transform many equalities.

• Some programming languages define $\%q$ differently such as a function from $\Bbb Z$ to a different set. It does not affect the proof above since all of them satisfy $x\%q-x$ is a multiple of $q$ and $x\%q=y\%q$ when the difference between $x$ and $y$ is a multiple or $q$, i.e., when $x\!\!\pmod q=y \!\!\pmod q$. Dec 17, 2022 at 20:01
• Yes, I think I meant the modulo operation as in $\%q$, but could you elaborate on the second to last step? Why is that a multiple of $q$? Sorry but I just can't see it. Dec 17, 2022 at 22:16
• @giofrida Is it clearer now? Dec 18, 2022 at 6:12
• Yes, thank you. Dec 18, 2022 at 12:59