Rabin Karp string matching algorithm. Coding interview questions.

Interview question: Find the first occurrence of a substring.
Given two strings s the search string and p the pattern string find the first occurrence of p in s.
We can solve this problem in O(n+m) time complexity using Rabin Karp algorithm.
There are 3 linear time string matching algorithms: KMP, Boyer-Moore, and Rabin Karp.
Rabin Karp is the simplest string matching algorithm, easy to understand, and easy to explain in a coding interview.
We use the technique of #Rollinghash to calculate the hash value of substrings.

Wiki definition:
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern.

[md.shazidalhasan]

The only question I had throughout the entire video was answered in 5 sec 😅

[hasanuzzaman]

I am a bit confused. Will not it be `hash = hash * base + ord(new_char)` when we add a new character to the existing hash? (after removing the first char and during adding new char)