Limitations of Rabin-Karp Algorithm
Spurious Hit: When the hash value of the pattern matches with the hash value of a window of the text but the window is not the actual pattern then it is called a spurious hit. Spurious hit increases the time complexity of the algorithm. In order to minimize spurious hit, we use good hash function. It greatly reduces the spurious hit.
Related Posts:
Searching for Patterns | Set 1 (Naive Pattern Searching)
Searching for Patterns | Set 2 (KMP Algorithm)
Rabin-Karp Algorithm for Pattern Searching
Given a text T[0. . .n-1] and a pattern P[0. . .m-1], write a function search(char P[], char T[]) that prints all occurrences of P[] present in T[] using Rabin Karp algorithm. You may assume that n > m.
Examples:
Input: T[] = “THIS IS A TEST TEXT”, P[] = “TEST”
Output: Pattern found at index 10Input: T[] = “AABAACAADAABAABA”, P[] = “AABA”
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
Contact Us