Log inSign up
mediumgeeksforgeeksNot Started

Rabin Karp Pattern Matching

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on geeksforgeeks
Lesson

Problem Statement

Given two strings, one is a text string txt and other is a pattern string pat. The task is to print all the 0-based starting indexes of the occurrences of the pattern string in the text string using the Rabin-Karp Algorithm.

If the pattern does not occur in the text, return an empty list.

Example 1 · Example:

Input: txt = "AABAACAADAABAABA", pat = "AABA"
Output: [0, 9, 12]
Explanation: Pattern "AABA" appears at indices 0, 9, and 12 in the text.

Example 2 · Example:

Input: txt = "GEEKS FOR GEEKS", pat = "GEEK"
Output: [0, 10]
Explanation: Pattern "GEEK" appears at indices 0 and 10.

Example 3 · Example:

Input: txt = "HELLO WORLD", pat = "PYTHON"
Output: []
Explanation: Pattern does not appear in the text.

Constraints:

  • 1 <= txt.length, pat.length <= 105
  • txt and pat consist of lowercase and uppercase English alphabets.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master polynomial rolling hash computation.
  • Correctly implement modular arithmetic with negative wrapping.
  • Handle spurious hash collisions cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Searching for single or multiple patterns inside a long text stream.
  • Detecting duplicate substrings with rolling fingerprints.

Algorithmic Decision Tree:

  • Polynomial Rolling Hash
  • Sliding Window Modulo State

Connected Patterns:

KMP Pattern MatchingLongest Duplicate SubstringRepeated DNA Sequences

1. Naive String Search

Intuition

For each position i from 0 to n - m, compare txt[i + j] with pat[j] for j from 0 to m - 1. If all match, record i.

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize res = [].
  2. For i from 0 to n - m:
  3. match = true
  4. For j from 0 to m - 1:
  5. If txt[i + j] != pat[j]: match = false; break.
  6. If match: res.push(i).
  7. Return res.

Naive String Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [G, E, E, K, S, , F, O, R, ]
Current operationSTEP 1 OF 6
Observation: Outer loop starts at index $i = 0$
Visual state
Values and pointers at this exact step
array
S
G
E
E
K
S
F
O
R
0
↑ i=0
1
2
3
↑ text[0..3] vs 'GEEK'
4
5
6
7
8
9
Variables at this step
i
0
window
GEEK
match
true
results
[0]
Check / comparison
Compare text[0..3] ('GEEK') with pattern 'GEEK'.
Decision / next transition
All 4 characters match! Match found at index 0. Results: [0].
Why this step matters

Observation: Outer loop starts at index i = 0. Pattern length M = 4.

Decision: Compare character-by-character: G==G, E==E, E==E, K==K. Match at index 0! Add to results: [0].

Invariant: Character-by-character loop verifies exact matches.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> search(std::string pat, std::string txt) {
8 std::vector<int> res;
9 int n = txt.size(), m = pat.size();
10 if (n < m) return res;
11
12 for (int i = 0; i <= n - m; ++i) {
13 int j = 0;
14 while (j < m && txt[i + j] == pat[j]) j++;
15 if (j == m) res.push_back(i);
16 }
17 return res;
18 }
19};
20
21int main() {
22 Solution sol;
23 auto ans = sol.search("AABA", "AABAACAADAABAABA");
24 for (int x : ans) std::cout << x << " "; // 0 9 12
25 std::cout << std::endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — Performs up to (N - M + 1) * M character comparisons.
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

Rolling hash skips expensive full-string comparisons for 99.9% of non-matching positions.

Operates in O(1) auxiliary space using a few primitive integer registers.

2. Double Hash Rolling Window

Intuition

Maintain two distinct prime moduli Q1 = 10^9+7 and Q2 = 10^9+9. Compute hash pairs (p1, p2) for pattern and (t1, t2) for the text window. Two hashes matching simultaneously has collision probability ~10^-18, allowing instant match confirmation.

When to apply: When character verification step cannot be executed in-place.

Algorithm

  1. Initialize two primes Q1 = 1e9+7, Q2 = 1e9+9.
  2. Calculate initial hash pairs for pattern and first window.
  3. Slide window, updating both hashes concurrently in O(1).
  4. If p1 == t1 && p2 == t2, append index i.
  5. Return result.

Double Hash Rolling Window

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [G, E, E, K, S, , F, O, R, ]
Current operationSTEP 1 OF 6
Observation: Use two distinct prime bases and moduli to prevent hash collisions
Visual state
Values and pointers at this exact step
array
S
G
E
E
K
S
F
O
R
0
↑ H1, H2 MATCH
1
2
3
4
5
6
7
8
9
Variables at this step
idx
0
h1Match
true
h2Match
true
results
[0]
Check / comparison
Compute dual hashes (B1=31, M1=1e9+7) and (B2=37, M2=1e9+9).
Decision / next transition
Window [0..3] dual hash matches pattern dual hash! Record index 0.
Why this step matters

Observation: Use two distinct prime bases and moduli to prevent hash collisions.

Decision: At window [0..3] = 'GEEK', both H_1 and H_2 match pattern hashes. Probability of collision < 10^{-18}; record index 0.

Invariant: Double hashing eliminates false positive hash collisions without explicit string verification.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> search(std::string pat, std::string txt) {
8 std::vector<int> res;
9 int n = txt.size(), m = pat.size();
10 if (n < m) return res;
11
12 long long d = 256, q1 = 1000000007, q2 = 1000000009;
13 long long p1 = 0, p2 = 0, t1 = 0, t2 = 0;
14 long long h1 = 1, h2 = 1;
15
16 for (int i = 0; i < m - 1; ++i) {
17 h1 = (h1 * d) % q1;
18 h2 = (h2 * d) % q2;
19 }
20
21 for (int i = 0; i < m; ++i) {
22 p1 = (d * p1 + pat[i]) % q1;
23 p2 = (d * p2 + pat[i]) % q2;
24 t1 = (d * t1 + txt[i]) % q1;
25 t2 = (d * t2 + txt[i]) % q2;
26 }
27
28 for (int i = 0; i <= n - m; ++i) {
29 if (p1 == t1 && p2 == t2) {
30 res.push_back(i);
31 }
32 if (i < n - m) {
33 t1 = (d * (t1 - txt[i] * h1) + txt[i + m]) % q1;
34 if (t1 < 0) t1 += q1;
35 t2 = (d * (t2 - txt[i] * h2) + txt[i + m]) % q2;
36 if (t2 < 0) t2 += q2;
37 }
38 }
39 return res;
40 }
41};
42
43int main() {
44 Solution sol;
45 auto ans = sol.search("GEEK", "GEEKS FOR GEEKS");
46 for (int x : ans) std::cout << x << " "; // 0 10
47 std::cout << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N + M) — Both hash updates run in O(1) arithmetic operations per character.
  • Space complexity: O(1)

3. Rabin-Karp Rolling Hash with Collision Verification (Optimal)

Intuition

Compute hash p of pattern and t of initial text window of size M under base d = 256 and prime q = 10^9 + 7. Calculate high-power factor h = (d^(m - 1)) % q. Slide the window: if p == t, verify all M characters. Then update t = (d * (t - txt[i] * h) + txt[i + m]) % q and wrap negative values with t += q.

When to apply: The standard gold standard formulation required in technical interviews.

Algorithm

  1. Let d = 256, q = 1000000007.
  2. Compute h = (d^(m - 1)) % q.
  3. Calculate p (pattern hash) and initial t (text window hash).
  4. Loop i from 0 to n - m:
  5. If p == t:
  6. Verify txt[i...i + m - 1] == pat. If identical, add i to results.
  7. If i < n - m:
  8. t = (d * (t - txt[i] * h) + txt[i + m]) % q
  9. If t < 0: t += q.
  10. Return results array.

Rolling Hash Modulo Polynomial Fingerprint

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [G, E, E, K, S, , F, O, R, ]
Current operationSTEP 1 OF 6
Observation: Compute polynomial rolling hash for pattern "GEEK" ($M=4$)
Visual state
Values and pointers at this exact step
array
S
G
E
E
K
S
0
↑ L=0
1
2
3
↑ R=3 (Window 0)
4
Variables at this step
M
4
patternHash
12345
currentWindowHash
12345
hashMatch
true
Why this step matters

Observation: Compute polynomial rolling hash for pattern "GEEK" (M=4). Compute hash for first window txt[0..3] ("GEEK").

Decision: Hash values match! Perform character-by-character verification: exact match confirmed at index 0.

Invariant: Matching hashes warrant O(M) exact verification.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> search(std::string pat, std::string txt) {
8 std::vector<int> res;
9 int n = txt.size(), m = pat.size();
10 if (n < m) return res;
11
12 long long d = 256, q = 1000000007;
13 long long p = 0, t = 0, h = 1;
14
15 for (int i = 0; i < m - 1; ++i) {
16 h = (h * d) % q;
17 }
18
19 for (int i = 0; i < m; ++i) {
20 p = (d * p + pat[i]) % q;
21 t = (d * t + txt[i]) % q;
22 }
23
24 for (int i = 0; i <= n - m; ++i) {
25 if (p == t) {
26 bool match = true;
27 for (int j = 0; j < m; ++j) {
28 if (txt[i + j] != pat[j]) {
29 match = false;
30 break;
31 }
32 }
33 if (match) res.push_back(i);
34 }
35 if (i < n - m) {
36 t = (d * (t - txt[i] * h) + txt[i + m]) % q;
37 if (t < 0) t += q;
38 }
39 }
40 return res;
41 }
42};
43
44int main() {
45 Solution sol;
46 auto ans = sol.search("AABA", "AABAACAADAABAABA");
47 for (int x : ans) std::cout << x << " "; // 0 9 12
48 std::cout << std::endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N + M) average, O(N * M) worst case — Rolling hash update is O(1). M-character verification only triggers when hashes match.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Brute Force SearchO((N - M + 1) * M)O(1)Simple to write.Degrades to O(N * M) on repetitive text.
2.Rabin-Karp Rolling Hash (Single Modulo)O(N + M) average, O(N * M) worst caseO(1) extra spaceExtremely fast on average; easily scales to multiple pattern matching.Requires character validation on hash matches.
3.Double Hashing Rabin-KarpOptimalO(N + M) with probability 1 - 10^-18 collisionO(1) extra spaceVirtually zero collisions without needing character verification.Calculates two distinct hash values per window.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not handling negative results from (t - txt[i] * h) in C++/Java modulo operations.

Pitfall 2:

Omitting the character check upon hash match, which fails on hash collisions.

Crucial Edge Cases to Validate:

  • pat.length > txt.length: Returns empty list [] immediately.
  • Negative modulo result after subtraction: Normalized with if (t < 0) t += q to ensure non-negative remainder.
  • Spurious hash collision (hash matches but characters differ): Explicit loop txt[i...i+m-1] == pat discards false positives.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Derive the rolling hash update formula explicitly: t = (d * (t - txt[i] * h) + txt[i + m]) % q.
  2. Explain why handling negative modulo is required in C++ and Java.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the character check necessary even when pattern hash p equals window hash t?

Back to DSA Sheet