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:

 1def rabin_karp(text, pattern):
 2    n = len(text)
 3    m = len(pattern)
 4    d = 256  # number of characters in the input alphabet
 5    q = 101  # a prime number
 6    h = pow(d, m-1) % q
 7    p = 0  # hash value for pattern
 8    t = 0  # hash value for text
 9    results = []
10
11    # Calculate the hash value of pattern and first window of text
12    for i in range(m):
13        p = (d * p + ord(pattern[i])) % q
14        t = (d * t + ord(text[i])) % q
15
16    # Slide the pattern over text one by one
17    for i in range(n - m + 1):
18        # Check the hash values of current window of text and pattern
19        if p == t:
20            # If the hash values match, check for characters one by one
21            if text[i:i+m] == pattern:
22                results.append(i)
23
24        # Calculate hash value for next window of text
25        if i < n - m:
26            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
27
28            # We might get negative value of t, converting it to positive
29            if t < 0:
30                t = t + q
31
32    return results
33
34# Example usage
35text = "ABABDABACDABABCABAB"
36pattern = "ABABCABAB"
37matches = rabin_karp(text, pattern)
38print(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.

Solution#

 1# Exercise 1: Search for MULTIPLE patterns at once with Rabin-Karp.
 2# All patterns must share the same length so one rolling hash serves them all.
 3def rabin_karp_multi(text, patterns):
 4    if not patterns:
 5        return {}
 6    m = len(patterns[0])
 7    assert all(len(p) == m for p in patterns), "Patterns must be equal length"
 8
 9    d, q = 256, 1_000_000_007  # Base and a large prime modulus.
10    high = pow(d, m - 1, q)
11
12    # Hash every pattern once, grouping patterns that share a hash.
13    pattern_hashes = {}
14    for p in patterns:
15        h = 0
16        for ch in p:
17            h = (d * h + ord(ch)) % q
18        pattern_hashes.setdefault(h, []).append(p)
19
20    results = {p: [] for p in patterns}
21    if len(text) < m:
22        return results
23
24    t = 0
25    for i in range(m):  # Hash the first window of the text.
26        t = (d * t + ord(text[i])) % q
27
28    for i in range(len(text) - m + 1):
29        if t in pattern_hashes:
30            window = text[i:i + m]
31            for p in pattern_hashes[t]:
32                if window == p:  # Confirm to guard against hash collisions.
33                    results[p].append(i)
34        if i < len(text) - m:  # Roll the hash to the next window.
35            t = (d * (t - ord(text[i]) * high) + ord(text[i + m])) % q
36    return results
37
38text = "AABAACAADAABAABA"
39print(rabin_karp_multi(text, ["AABA", "AADA"]))
40# {'AABA': [0, 9, 12], 'AADA': [6]}

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