DAA: Rabin Karp Algorithm
The Rabin Karp or Karp Rabin algorithm is used to matching a specific pattern in the string.
It uses the technique of hashing to match a specific text.
There also exists a naive algorithm for pattern matching. The naive algorithm iterates in the whole string one by one matching each character of our pattern.
Rabin Karp works in a different manner. It uses the hash function, a tool in which we match the larger input value to a smaller output value.
The algorithm calculates the hash value of the pattern and the current substring in the given string. If both hash and pattern values match, it then matches the individual letter in a string with the pattern.
So the main task here is to find the correct hash value of the length of the pattern then match it.
The hash function in this algorithm calculates an integer value, and this integer value of the string is basically the numeric value of the string.
As there can be larger values of pattern, the numeric values cannot be stored in the form of integers. This optimization is done using modular arithmetic.
