Code Notes made by Vaibhav Rathod

Rabin-Karp Algorithm

2 min read

Written by Vaibhav Rathod

Explanation

  • The Rabin-Karp Algorithm is a string searching algorithm used to find a pattern within a larger text. It uses a hashing technique to perform efficient string matching. The idea behind Rabin-Karp is to compare the hash values of the pattern and substrings of the text. If the hash values match, we then perform an actual string comparison to check for a real match.

Steps:

  • Compute the hash of the pattern and the first window of the text.
  • Compare the hash of each substring in the text with the hash of the pattern.
  • If the hashes match, compare the actual strings of the pattern and the substring.
  • Repeat the process for all possible windows in the text.

Time Complexity:

  • The worst-case time complexity is O(n*m), where n is the size of the text and m is the size of the pattern.
  • The average-case time complexity is O(n + m), provided hashing is done efficiently.
def rabin_karp(text, pattern):
    n = len(text)
    m = len(pattern)
    d = 256  # Number of characters in the input alphabet
    q = 101  # A prime number to perform modulus operation
    
    # Calculate hash value of the pattern and first window of the text
    p_hash = 0
    t_hash = 0
    for i in range(m):
        p_hash = (p_hash * d + ord(pattern[i])) % q
        t_hash = (t_hash * d + ord(text[i])) % q
    
    # Check for pattern match
    for i in range(n - m + 1):
        if p_hash == t_hash:  # Hashes match, compare strings
            if text[i:i + m] == pattern:
                print(f"Pattern found at index {i}")
        
        if i < n - m:
            # Update hash value for next window
            t_hash = (d * (t_hash - ord(text[i]) * (d ** (m - 1))) + ord(text[i + m])) % q
            if t_hash < 0:
                t_hash += q
 
# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
rabin_karp(text, pattern)

Graph View

Backlinks

Recently Updated