Day 57: Rabin-Karp Algorithm

Table of Contents

Day 57: Rabin-Karp Algorithm #

Welcome to Day 57 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Rabin-Karp algorithm, another efficient string matching algorithm that uses hashing to find patterns in text.

What is the Rabin-Karp Algorithm? #

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find patterns in strings. It was created by Richard M. Karp and Michael O. Rabin in 1987. The algorithm is particularly useful for multi-pattern search.

How Rabin-Karp Works #

The key ideas behind the Rabin-Karp algorithm are:

  1. Use a hash function to convert the pattern and substrings of the text to numeric values.
  2. Compare the hash values instead of comparing the strings character by character.
  3. If the hash values match, then perform a character-by-character comparison to confirm the match.

The algorithm uses a rolling hash function, which allows it to efficiently compute hash values for subsequent substrings.

Implementation #

Here’s a Python implementation of the Rabin-Karp algorithm:

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
    h = pow(d, m-1) % q
    p = 0  # hash value for pattern
    t = 0  # hash value for text
    results = []

    # Calculate the hash value of pattern and first window of text
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[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 p == t:
            # If the hash values match, check for characters one by one
            if text[i:i+m] == pattern:
                results.append(i)

        # Calculate hash value for next window of text
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q

            # We might get negative value of t, converting it to positive
            if t < 0:
                t = t + q

    return results

# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
matches = rabin_karp(text, pattern)
print(f"Pattern found at indices: {matches}")

Time Complexity #

  • Average and Best Case: O(n + m), where n is the length of the text and m is the length of the pattern
  • Worst Case: O(nm), which occurs when all hash values match but the substrings don’t

Space Complexity #

The space complexity is O(1) as it uses a constant amount of extra space.

Advantages of Rabin-Karp #

  1. Efficient for multiple pattern searching
  2. Works well with large texts and patterns
  3. Can be extended to two-dimensional pattern matching

Disadvantages of Rabin-Karp #

  1. Worst-case time complexity is still O(nm)
  2. Effectiveness depends on the choice of the hash function
  3. May have issues with very short patterns

Applications of Rabin-Karp #

  1. Plagiarism detection
  2. Intrusion detection systems
  3. Finding DNA sequences in computational biology
  4. File similarity detection

Variations and Optimizations #

  1. Use of better hash functions to reduce collisions
  2. Parallelization for searching multiple patterns simultaneously
  3. Use of prime numbers in hash function to reduce false positives

Exercise #

  1. Modify the Rabin-Karp algorithm to search for multiple patterns simultaneously.
  2. Implement a 2D version of the Rabin-Karp algorithm for pattern matching in a matrix.
  3. Use the Rabin-Karp algorithm to find the longest repeated substring in a given string.

Summary #

Today, we explored the Rabin-Karp algorithm, an efficient string matching algorithm that uses hashing to find patterns in text. We implemented the algorithm, discussed its time and space complexity, and looked at its advantages, disadvantages, and applications.

The Rabin-Karp algorithm’s use of hashing makes it particularly useful for multi-pattern searching and in scenarios where we need to find similarities between strings. Understanding this algorithm adds another powerful tool to your string processing toolkit.

Tomorrow, we’ll dive into Tries, a tree-like data structure used for efficient retrieval of strings. Stay tuned!