Rabin Karp String Matching in DSA C# - Time & Space Complexity

Time Complexity: Rabin Karp String Matching

O(n + m)

Understanding Time Complexity

We want to understand how the Rabin Karp algorithm's running time changes as the text and pattern sizes grow.

Specifically, how many steps does it take to find a pattern in a text?

Scenario Under Consideration

Analyze the time complexity of the following Rabin Karp code snippet.

public bool RabinKarp(string text, string pattern) {
    int n = text.Length, m = pattern.Length;
    if (m == 0) return true;
    if (m > n) return false;
    int prime = 101, baseVal = 256;
    long patternHash = 0, textHash = 0, h = 1;

    for (int i = 0; i < m - 1; i++)
        h = (h * baseVal) % prime;

    for (int i = 0; i < m; i++) {
        patternHash = (baseVal * patternHash + pattern[i]) % prime;
        textHash = (baseVal * textHash + text[i]) % prime;
    }

    for (int i = 0; i < n - m + 1; i++) {
        if (patternHash == textHash) {
            // Check characters one by one
            int j;
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) break;
            }
            if (j == m) return true;
        }
        if (i < n - m) {
            textHash = (baseVal * (textHash - text[i] * h) + text[i + m]) % prime;
            if (textHash < 0) textHash += prime;
        }
    }
    return false;
}
    

This code searches for a pattern in a text using hashing to speed up comparisons.

Identify Repeating Operations

Identify the loops and repeated checks.

• Primary operation: Sliding over the text with a loop that runs (n - m + 1) times.
• How many times: For each position, it compares hashes and sometimes characters one by one (up to m times).

How Execution Grows With Input

As the text length (n) grows, the main loop runs roughly n times. The pattern length (m) affects how many characters we check when hashes match.

Input Size (n)	Approx. Operations
10	About 10 hash checks, few character checks
100	About 100 hash checks, some character checks
1000	About 1000 hash checks, some character checks

Pattern length m affects character checks only when hashes match, which is rare if hash is good.

So, execution grows mostly linearly with text size.

Final Time Complexity

Time Complexity: O(n + m)

This means the algorithm checks the text and pattern mostly once each, making it efficient for large inputs.

Common Mistake

[X] Wrong: "Rabin Karp always compares every character in the text to the pattern."

[OK] Correct: It uses hashing to skip many character comparisons, only checking characters when hashes match, which is rare.

Interview Connect

Understanding Rabin Karp's time complexity shows you can analyze how hashing helps speed up searching, a useful skill for many coding problems.

Self-Check

"What if we used a larger prime number for hashing? How would that affect the time complexity?"

Practice

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

easy

A. Sort the text and pattern before matching

B. Compare each character of pattern with text directly

C. Use hashing to find pattern matches efficiently

D. Use recursion to find all pattern occurrences

Solution

1. Step 1: Understand Rabin Karp approach

   Rabin Karp uses hashing to convert strings into numbers for quick comparison.

2. Step 2: Compare hash values instead of characters

   It compares hash of pattern with hash of text substrings to find matches efficiently.

3. Final Answer:

   Use 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 one by one always
• Confusing with brute force matching
• Assuming sorting is involved

2. Which of the following is the correct way to calculate the initial hash for a substring in Rabin Karp (assuming base = 256 and prime = 101)?

easy

A. hash = (hash - char) % prime

B. hash = (hash + base * char) % prime

C. hash = (char * base) % prime

D. hash = (hash * base + char) % prime

Solution

1. Step 1: Understand rolling hash formula

   The rolling hash updates as hash = (hash * base + new_char) % prime.

2. Step 2: Apply formula for initial hash

   Initial hash is calculated by iterating characters and applying this formula cumulatively.

3. Final Answer:

   hash = (hash * base + char) % prime -> Option D

4. Quick Check:

   Rolling hash formula = hash = (hash * base + char) % prime [OK]

Hint: Use (hash * base + char) % prime for rolling hash [OK]

Common Mistakes:

• Adding instead of multiplying by base
• Subtracting characters incorrectly
• Ignoring modulo operation

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

string text = "ababc";
string pattern = "abc";
List<int> matches = RabinKarpSearch(text, pattern);
Console.WriteLine(string.Join(",", matches));

List<int> RabinKarpSearch(string txt, string pat) {
    int baseVal = 256, prime = 101;
    int m = pat.Length, n = txt.Length;
    int patHash = 0, txtHash = 0, h = 1;
    List<int> result = new List<int>();

    for (int i = 0; i < m - 1; i++) h = (h * baseVal) % prime;

    for (int i = 0; i < m; i++) {
        patHash = (baseVal * patHash + pat[i]) % prime;
        txtHash = (baseVal * txtHash + txt[i]) % prime;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patHash == txtHash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (txt[i + j] != pat[j]) {
                    match = false;
                    break;
                }
            }
            if (match) result.Add(i);
        }
        if (i < n - m) {
            txtHash = (baseVal * (txtHash - txt[i] * h) + txt[i + m]) % prime;
            if (txtHash < 0) txtHash += prime;
        }
    }
    return result;
}

medium

A. 1,2

B. 2

C. 0,2

D. No matches

Solution

1. Step 1: Identify pattern occurrences in text

   Pattern "abc" appears starting at index 2 in "ababc". Also, substring at index 0 is "aba" which is not a match.

2. Step 2: Check hash and character matches

   Hashes match only at index 2 (initial hashes differ at index 0 and 1), and character check passes at index 2. So only index 2 is added.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found at index 2 [OK]

Hint: Check both hash and characters to confirm matches [OK]

Common Mistakes:

• Assuming all hash matches are valid
• Ignoring character verification after hash match
• Miscounting indices starting from 1

4. Identify the bug in this Rabin Karp substring search code snippet:

int baseVal = 256, prime = 101;
int m = pattern.Length, n = text.Length;
int patHash = 0, txtHash = 0, h = 1;
for (int i = 0; i <= m - 1; i++) h = (h * baseVal) % prime;
for (int i = 0; i < m; i++) {
    patHash = (baseVal * patHash + pattern[i]) % prime;
    txtHash = (baseVal * txtHash + text[i]) % prime;
}
// rest of code omitted

medium

A. Loop for h calculation should run till m-2, not m-1

B. Modulo prime missing in hash calculations

C. Using <= in loop causes out of range error

D. Base value should be 128, not 256

Solution

1. Step 1: Analyze h calculation loop

   h is used as base^(m-1) % prime, so loop should run m-1 times, i.e., i from 0 to m-2.

2. Step 2: Identify off-by-one error

   Loop runs from i=0 to i=m-1 (inclusive), which is m times, causing incorrect h value.

3. Final Answer:

   Loop for h calculation should run till m-2, not m-1 -> Option A

4. Quick Check:

   h loop runs m-1 times [OK]

Hint: Calculate h with loop running m-1 times only [OK]

Common Mistakes:

• Using <= instead of < in loop
• Forgetting modulo in hash updates
• Wrong base value choice

5. You want to find all occurrences of pattern "test" in a very large text using Rabin Karp. Which optimization helps reduce false positives caused by hash collisions?

hard

A. Use a larger prime number for modulo operations

B. Skip character comparison after hash match

C. Use base value as 1 to simplify hash

D. Only check first character after hash match

Solution

1. Step 1: Understand hash collisions in Rabin Karp

   Hash collisions occur when different substrings produce same hash value, causing false positives.

2. Step 2: Use larger prime to reduce collisions

   A larger prime number reduces chances of collisions by spreading hash values more evenly.

3. Final Answer:

   Use a larger prime number for modulo operations -> Option A

4. Quick Check:

   Larger prime = fewer collisions [OK]

Hint: Choose bigger prime to minimize hash collisions [OK]

Common Mistakes:

• Skipping character checks after hash match
• Using base 1 which weakens hash uniqueness
• Checking only first character after hash match