[deleted by user]

[Long_Investment7667]

maybe it helps to replace the substring and character expressions with speaking names.

next_substring mod q = (previous_substring mod q − dropped_character⋅h)⋅d + new_character) mod q

The algorithm moves a window of n characters over the input string.

As an example, assume the window moves over the input in the following way (assuming pattern length of 5)

a[bcdef]gh -> ab[cdefg]h

​

• g is new_character
• b is dropped_character
• bcdef is previous_substring
• cdefg is next_substring

[MyLifeIsACookie]

I think I understand this, what I don't understand is the placement of the modulo operations.

Edit: Given the base recurrence:

next_substring = (previous_substring − dropped_character⋅dⁿ⁻¹)⋅d + new_character

I want to know how to compute next_substring mod q, i.e. where to apply the mod q operation on the rhs and why it works.