Rabin Karp String Matching in DSA Java

Mental Model

We use a rolling number code for strings to quickly find a pattern inside a text by comparing these codes instead of characters.

Analogy: Imagine checking if a small book page is inside a big book by comparing the sum of letter values instead of reading every letter each time.

Text:  T h i s   i s   a   t e x t
Pattern:     i s   a
Hash codes: [T=84][h=104][i=105][s=115] ...
               ↑
            Sliding window over text

Dry Run Walkthrough

Input: text: "ababcabc", pattern: "abc"

Goal: Find all starting positions where pattern "abc" appears in text

Step 1: Calculate hash of pattern "abc" and first window "aba" in text

pattern hash = hash("abc")
window hash = hash("aba")

Why: We need initial hashes to start comparing pattern with text windows

Step 2: Compare pattern hash with window hash at position 0

pattern hash != window hash ("abc" != "aba")

Why: Hashes differ, so pattern not found at index 0

Step 3: Slide window by 1: remove 'a', add 'b', recalculate window hash for "bab"

window hash = hash("bab")

Why: Update hash efficiently to check next substring

Step 4: Compare pattern hash with window hash at position 1

pattern hash != window hash ("abc" != "bab")

Why: Hashes differ, pattern not found at index 1

Step 5: Slide window by 1: remove 'b', add 'c', recalculate window hash for "abc"

window hash = hash("abc")

Why: Update hash for next substring to compare

Step 6: Compare pattern hash with window hash at position 2

pattern hash == window hash, verify characters match

Why: Hashes match, verify actual substring to avoid false positive

Step 7: Confirm substring "abc" matches pattern at index 2

Pattern found at index 2

Why: Exact match found, record position

Step 8: Continue sliding window and checking until end of text

Pattern also found at index 5

Why: Find all occurrences of pattern

Result:

Final matches at indices: 2, 5

Annotated Code

DSA Java

public class RabinKarp {
    static final int d = 256; // number of characters in input alphabet
    static final int q = 101; // a prime number for modulo

    public static void search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();
        int i, j;
        int p = 0; // hash value for pattern
        int t = 0; // hash value for text window
        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 (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
            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);
            }
        }
    }

    public static void main(String[] args) {
        String txt = "ababcabc";
        String pat = "abc";
        search(pat, txt);
    }
}

for (i = 0; i < M - 1; i++) h = (h * d) % q;

Calculate highest power of d needed for rolling hash

for (i = 0; i < M; i++) { p = (d * p + pat.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; }

Compute initial hash for pattern and first text window

for (i = 0; i <= N - M; i++) {

Slide window over text from start to end

if (p == t) { for (j = 0; j < M; j++) { if (txt.charAt(i + j) != pat.charAt(j)) break; } if (j == M) System.out.println("Pattern found at index " + i); }

If hashes match, verify characters to confirm pattern

if (i < N - M) { t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q; if (t < 0) t = (t + q); }

Update rolling hash for next window, handle negative hash

Output

Pattern found at index 2

Pattern found at index 5

Complexity Analysis

Time: O(N + M) on average because we compute hash once and slide over text with constant time updates; worst case O(N*M) if many hash collisions

Space: O(1) because only fixed extra variables are used regardless of input size

vs Alternative: Compared to naive string matching O(N*M), Rabin-Karp is faster on average due to hashing but can degrade if many collisions occur

Edge Cases

Empty text

No matches found, function completes without output

DSA Java

for (i = 0; i <= N - M; i++) {

Pattern longer than text

Loop does not run, no matches found

DSA Java

for (i = 0; i <= N - M; i++) {

Pattern equals text

Single match found at index 0

DSA Java

if (p == t) {

When to Use This Pattern

When you need to find a substring pattern in a large text efficiently, especially when multiple matches are possible, Rabin-Karp is a good choice because it uses hashing to speed up comparisons.

Common Mistakes

Mistake: Not handling negative hash values after rolling hash update
Fix: Add code to convert negative hash to positive by adding modulo q

Mistake: Skipping character-by-character check after hash match, causing false positives
Fix: Always verify characters when hashes match to confirm actual pattern

Summary

It finds all occurrences of a pattern string inside a text using rolling hash to speed up comparisons.

Use it when you want faster substring search than naive methods, especially with multiple pattern matches.

The key insight is using a rolling hash to quickly update and compare substring codes instead of characters.

Practice

1. What is the main idea behind the Rabin Karp String Matching algorithm?

easy

A. It sorts the text and pattern before matching

B. It compares each character one by one without hashing

C. It uses hashing to find pattern matches efficiently

D. It uses recursion to find the pattern

Solution

1. Step 1: Understand Rabin Karp's approach

   The algorithm uses a hash function to convert the pattern and text substrings into numbers.

2. Step 2: Use hashing for efficient matching

   By comparing hash values instead of characters, it quickly finds potential matches.

3. Final Answer:

   It uses hashing to find pattern matches efficiently -> Option C

4. Quick Check:

   Hashing = Efficient matching [OK]

Hint: Remember Rabin Karp uses hashing for fast pattern search [OK]

Common Mistakes:

• Thinking it compares characters directly without hashing
• Confusing it with brute force matching
• Assuming it sorts strings before matching

2. Which of the following is the correct way to calculate the rolling hash in Rabin Karp for the next substring?

easy

A. new_hash = (old_hash - old_char * high_base) * base + new_char

B. new_hash = old_hash + old_char + new_char

C. new_hash = old_hash * old_char - new_char

D. new_hash = old_hash / base + new_char * high_base

Solution

1. Step 1: Recall rolling hash formula

   Rolling hash removes the old char's contribution and adds the new char's value.

2. Step 2: Apply formula correctly

   It subtracts old_char * high_base, multiplies by base, then adds new_char.

3. Final Answer:

   new_hash = (old_hash - old_char * high_base) * base + new_char -> Option A

4. Quick Check:

   Rolling hash formula = new_hash = (old_hash - old_char * high_base) * base + new_char [OK]

Hint: Subtract old char, multiply, then add new char for rolling hash [OK]

Common Mistakes:

• Adding old_char instead of subtracting
• Dividing instead of multiplying by base
• Ignoring the high_base multiplier

3. What will be the output of the following Java code snippet using Rabin Karp to find pattern "abc" in text "ababc"?

String text = "ababc";
String pattern = "abc";
List<Integer> result = rabinKarpSearch(text, pattern);
System.out.println(result);

Assume rabinKarpSearch returns a list of starting indices where pattern matches.

medium

A. []

B. [0, 2]

C. [1]

D. [2]

Solution

1. Step 1: Identify pattern occurrences in text

   Text: "ababc"; pattern: "abc"; check substrings of length 3: "aba"(0), "bab"(1), "abc"(2).

2. Step 2: Find matching indices

   Only substring starting at index 2 matches "abc".

3. Final Answer:

   [2] -> Option D

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substrings of pattern length for exact matches [OK]

Common Mistakes:

• Including partial matches like "aba" or "bab"
• Assuming multiple matches without checking substring
• Confusing indices starting at 1 instead of 0

4. Consider this buggy Java snippet for Rabin Karp pattern search:

int base = 256;
int prime = 101;
int highBase = (int) Math.pow(base, pattern.length());
// ... rest of code
// rolling hash update:
currentHash = (currentHash - text.charAt(i) * highBase) * base + text.charAt(i + pattern.length());
currentHash %= prime;

What is the main bug here?

medium

A. highBase should be base^(pattern.length() - 1), not base^pattern.length()

B. Modulo operation should be before subtraction

C. Rolling hash should add old char, not subtract

D. Base should be 128, not 256

Solution

1. Step 1: Check highBase calculation

   High base is used to remove the leftmost character's contribution, so it should be base^(pattern length - 1).

2. Step 2: Identify incorrect power usage

   Using base^(pattern length) removes too much, causing wrong hash updates.

3. Final Answer:

   highBase should be base^(pattern.length() - 1), not base^pattern.length() -> Option A

4. Quick Check:

   Correct highBase power fixes rolling hash [OK]

Hint: Use base^(pattern length - 1) for highBase in rolling hash [OK]

Common Mistakes:

• Using base^pattern.length() instead of base^(pattern.length()-1)
• Ignoring modulo after subtraction
• Confusing addition and subtraction in rolling hash

5. You want to find all occurrences of pattern "aaa" in text "aaaaaa" using Rabin Karp. How many matches will the algorithm find and why?

hard

A. 2, because it skips overlapping matches

B. 4, because overlapping matches are counted

C. 3, because it counts only non-overlapping matches

D. 1, because it stops after first match

Solution

1. Step 1: Identify all substrings of length 3

   Text "aaaaaa" has substrings: "aaa"(0), "aaa"(1), "aaa"(2), "aaa"(3).

2. Step 2: Count overlapping matches

   All these substrings match pattern "aaa", so 4 matches found including overlaps.

3. Final Answer:

   4, because overlapping matches are counted -> Option B

4. Quick Check:

   Overlapping matches count = 4 [OK]

Hint: Rabin Karp counts overlapping matches by sliding one char at a time [OK]

Common Mistakes:

• Assuming matches cannot overlap
• Stopping search after first match
• Counting only non-overlapping matches