A naukri.com initiative
Prodevelopertutorial
2w
239
Introduction to Rabin Karp algorithm
- Rabin Karp algorithm uses a hash function and brute force approach to check if a pattern is present inside a string.
- Get the hash of the pattern and the hash of the whole string, and check if any hash value from substring matches our pattern hash.
- If the character are not same, it is called as spurious hit. The prime number can be random and larger the prime number, less chances of getting the same output from the hash function.
- In the above two steps, we are actually rolling over character by character, at any point we would have already calculated value for 2 characters.
- This method is called as the rolling hash method.
- When we find a match, we check if all the characters are the same. If the same we got out search pattern.
- If the hash value is the same but strings are different, we conclude that it is a spurious hit and check if there exist another hash value that is the same as our pattern hash.
- The Rabin-Karp algorithm uses a hash function to calculate the hash of the pattern.
- Then, it uses the hash of the pattern to compare with the hash of every n-length substring of the text using the rolling hash method.
- If a match is found using the hash values, the actual strings are compared by brute force to avoid spurious hits.
Read Full Article
14 Likes
For uninterrupted reading, download the app