Rabin Karp algorithm
Rabin-Karp algorithm is an algorithm used for searching/matching patterns in the text using a hash function. Unlike Naive string-matching algorithm, it does not travel through every character in the initial phase rather it filters the characters that do not match and then perform the comparison.
Rabin-Karp compares a string’s hash values, rather than the strings themselves. For efficiency, the hash value of the next position in the text is easily computed from the hash value of the current position.
Working of Rabin-Karp algorithm
- Initially calculate the hash value of the pattern P.
- Start iterating from the start of the string:
- Calculate the hash value of the current substring having length m.
- If the hash value of the current substring and the pattern are same check if the substring is same as the pattern.
- If they are same, store the starting index as a valid answer. Otherwise, continue for the next substrings.
- Return the starting indices as the required answer.
Example of Rabin Karp
Below is the implementation of the Rabin-Karp algorithm.
C++
/* Following program is a C++ implementation of Rabin Karp Algorithm given in the CLRS book */#include <bits/stdc++.h> using namespace std; // d is the number of characters in the input alphabet #define d 256 /* pat -> pattern txt -> text q -> A prime number */void search(char pat[], char txt[], int q) { int M = strlen(pat); int N = strlen(txt); int i, j; int p = 0; // hash value for pattern int t = 0; // hash value for txt int h = 1; // The value of h would be "pow(d, M-1)%q" for (i = 0; i < M - 1; i++) h = (h * d) % q; // Calculate the hash value of pattern and first // window of text for (i = 0; i < M; i++) { p = (d * p + pat[i]) % q; t = (d * t + txt[i]) % q; } // Slide the pattern over text one by one for (i = 0; i <= N - M; i++) { // Check the hash values of current window of text // and pattern. If the hash values match then only // check for characters one by one if (p == t) { /* Check for characters one by one */ for (j = 0; j < M; j++) { if (txt[i + j] != pat[j]) { break; } } // if p == t and pat[0...M-1] = txt[i, i+1, // ...i+M-1] if (j == M) cout << "Pattern found at index " << i << endl; } // Calculate hash value for next window of text: // Remove leading digit, add trailing digit if (i < N - M) { t = (d * (t - txt[i] * h) + txt[i + M]) % q; // We might get negative value of t, converting // it to positive if (t < 0) t = (t + q); } } } /* Driver code */int main() { char txt[] = "GEEKS FOR GEEKS"; char pat[] = "GEEK"; // we mod to avoid overflowing of value but we should // take as big q as possible to avoid the collison int q = INT_MAX; // Function Call search(pat, txt, q); return 0; } // This is code is contributed by rathbhupendra |
Java
import java.io.*; import java.lang.*; import java.util.*; /* pat -> pattern txt -> text q -> A prime number */public class GFG { // d is the number of characters in the input alphabet public final static int d = 256; public static void search(String pat, String txt, int q) { int M = pat.length(); int N = txt.length(); int i, j; int p = 0; // hash value for pattern int t = 0; // hash value for txt int h = 1; // The value of h would be "pow(d, M-1)%q" for (i = 0; i < M - 1; i++) h = (h * d) % q; // Calculate the hash value of pattern and first // window of text for (i = 0; i < M; i++) { p = (d * p + pat.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; } // Slide the pattern over text one by one for (i = 0; i <= N - M; i++) { // Check the hash values of current window of // text and pattern. If the hash values match // then only check for characters one by one if (p == t) { /* Check for characters one by one */ for (j = 0; j < M; j++) { if (txt.charAt(i + j) != pat.charAt(j)) { break; } } // if p == t and pat[0...M-1] = txt[i, i+1, // ...i+M-1] if (j == M) { System.out.println( "Pattern found at index " + i); } } // Calculate hash value for next window of text: // Remove leading digit, add trailing digit if (i < N - M) { t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q; // We might get negative value of t, // converting it to positive if (t < 0) t = (t + q); } } } /* Driver code */ public static void main(String[] args) { String txt = "GEEKS FOR GEEKS"; String pat = "GEEK"; // A prime number int q = 101; // Function Call search(pat, txt, q); } } // This code is contributed by ishankhandelwals. |
Python3
# d is the number of characters in the input alphabet d = 256 ''' pat -> pattern txt -> text q -> A prime number '''def search(pat, txt, q): M = len(pat) N = len(txt) p = 0 # hash value for pattern t = 0 # hash value for txt h = 1 # The value of h would be "pow(d, M-1)%q" for i in range(M - 1): h = (h * d) % q # Calculate the hash value of pattern and first # window of text for i in range(M): p = (d * p + ord(pat[i])) % q t = (d * t + ord(txt[i])) % q # Slide the pattern over text one by one for i in range(N - M + 1): # Check the hash values of current window of text # and pattern. If the hash values match then only # check for characters one by one if p == t: # Check for characters one by one for j in range(M): if txt[i + j] != pat[j]: break # if p == t and pat[0...M-1] = txt[i, i+1, # ...i+M-1] if j == M - 1: print("Pattern found at index " + str(i)) # Calculate hash value for next window of text: # Remove leading digit, add trailing digit if i < N - M: t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q # We might get negative value of t, converting # it to positive if t < 0: t = (t + q) # Driver code txt = "GEEKS FOR GEEKS"pat = "GEEK" # we mod to avoid overflowing of value but we should # take as big q as possible to avoid the collison q = float('inf') # Function Call search(pat, txt, q) # This code is contributed by akashish__ |
C#
// C# code using System; /* pat -> pattern txt -> text q -> A prime number */ class GFG { // d is the number of characters in the input alphabet public static int d = 256; public static void search(string pat, string txt, int q) { int M = pat.Length; int N = txt.Length; int i, j; int p = 0; // hash value for pattern int t = 0; // hash value for txt int h = 1; // The value of h would be "pow(d, M-1)%q" for (i = 0; i < M - 1; i++) h = (h * d) % q; // Calculate the hash value of pattern and first // window of text for (i = 0; i < M; i++) { p = (d * p + pat[i]) % q; t = (d * t + txt[i]) % q; } // Slide the pattern over text one by one for (i = 0; i <= N - M; i++) { // Check the hash values of current window of // text and pattern. If the hash values match // then only check for characters one by one if (p == t) { /* Check for characters one by one */ for (j = 0; j < M; j++) { if (txt[i + j] != pat[j]) { break; } } // if p == t and pat[0...M-1] = txt[i, i+1, // ...i+M-1] if (j == M) { Console.WriteLine( "Pattern found at index " + i); } } // Calculate hash value for next window of text: // Remove leading digit, add trailing digit if (i < N - M) { t = (d * (t - txt[i] * h) + txt[i + M]) % q; // We might get negative value of t, // converting it to positive if (t < 0) t = (t + q); } } } /* Driver code */ public static void Main(string[] args) { string txt = "GEEKS FOR GEEKS"; string pat = "GEEK"; // A prime number int q = 101; // Function Call search(pat, txt, q); } } // This code is contributed by akashish__ |
Javascript
// d is the number of characters in the input alphabet const d = 256; /* pat -> pattern txt -> text q -> A prime number */function search(pat, txt, q) { const M = pat.length; const N = txt.length; let p = 0; // hash value for pattern let t = 0; // hash value for txt let h = 1; // The value of h would be "pow(d, M-1)%q" for (let i = 0; i < M - 1; i++) { h = (h * d) % q; } // Calculate the hash value of pattern and first // window of text for (let i = 0; i < M; i++) { p = (d * p + pat.charCodeAt(i)) % q; t = (d * t + txt.charCodeAt(i)) % q; } // Slide the pattern over text one by one for (let i = 0; i <= N - M; i++) { // Check the hash values of current window of text // and pattern. If the hash values match then only // check for characters one by one if (p === t) { /* Check for characters one by one */ for (j = 0; j < M; j++) { if (txt.charAt(i + j) !== pat.charAt(j)) { break; } } // if p == t and pat[0...M-1] = txt[i, i+1, // ...i+M-1] if (j === M) console.log("Pattern found at index " + i); } // Calculate hash value for next window of text: // Remove leading digit, add trailing digit if (i < N - M) { t = (d * (t - txt.charCodeAt(i) * h) + txt.charCodeAt(i + M)) % q; // We might get negative value of t, converting // it to positive if (t < 0) t = (t + q); } } } /* Driver code */const txt = "GEEKS FOR GEEKS"; const pat = "GEEK"; // we mod to avoid overflowing of value but we should // take as big q as possible to avoid the collison const q = Number.MAX_SAFE_INTEGER; // Function Call search(pat, txt, q); // This code is contributed by ishankhandelwals. |
Output
Pattern found at index 0 Pattern found at index 10
Time Complexity:
- The average and best-case running time of the Rabin-Karp algorithm is O(n+m), but its worst-case time is O(nm).
- The worst case of the Rabin-Karp algorithm occurs when all characters of pattern and text are the same as the hash values of all the substrings of txt[] match with the hash value of pat[].
Space Complexity :
The space complexity of the Rabin-Karp algorithm is O(1), which means that it is a constant amount of memory that is required, regardless of the size of the input text and pattern. This is because the algorithm only needs to store a few variables that are updated as the algorithm progresses through the text and pattern. Specifically, the algorithm needs to store the hash value of the pattern, the hash value of the current window in the text, and a few loop counters and temporary variables. Since the size of these variables is fixed, the space complexity is constant.
Introduction to Pattern Searching – Data Structure and Algorithm Tutorial
Pattern searching is an algorithm that involves searching for patterns such as strings, words, images, etc.
We use certain algorithms to do the search process. The complexity of pattern searching varies from algorithm to algorithm. They are very useful when performing a search in a database. The Pattern Searching algorithm is useful for finding patterns in substrings of larger strings. This process can be accomplished using a variety of algorithms that we are going to discuss in this blog.
Introduction to Pattern Searching – Data Structure and Algorithm Tutorial
Contact Us