Jaspreet singh

Posted on Jun 30

Implement strStr() (Find the Index of the First Occurrence in a String) | Rabin-Karp

#algorithms #computerscience #interview #java

Problem Statement

Given two strings:

haystack

needle

Return the index of the first occurrence of needle in haystack.

If needle is not present, return -1.

Brute Force Intuition

In an interview, you can explain it like this:

Start matching needle from every possible index in haystack. If all characters match, return the current index.

This is straightforward but repeatedly compares the same characters.

Complexity

Time Complexity: O((N - M + 1) × M)
Space Complexity: O(1)

Where:

N = haystack.length()
M = needle.length()

Brute Force Code

class Solution {

    public int strStr(String haystack,
                      String needle) {

        int n = haystack.length();
        int m = needle.length();

        for (int i = 0; i <= n - m; i++) {

            int j = 0;

            while (j < m &&
                   haystack.charAt(i + j) ==
                   needle.charAt(j)) {

                j++;
            }

            if (j == m)
                return i;
        }

        return -1;
    }
}

Moving Towards the Optimal Approach

Notice that every shift compares almost the same characters again.

Instead of comparing characters,

compare:

Hash Values

If two hash values are different,

the strings are definitely different.

Only when the hashes match,

perform character comparison.

This is the idea behind the Rabin-Karp Algorithm.

Pattern Recognition

Whenever you see:

Pattern Searching
Substring Matching
Large Text Search

Think:

Rolling Hash (Rabin-Karp)

Key Observation

Compute:

Hash(needle)

Then compute the hash of every window of size:

needle.length()

Instead of recalculating from scratch,

update the hash in:

O(1)

using a Rolling Hash.

Optimal Approach

Step 1

Compute the hash of:

needle

Step 2

Compute the hash of the first window.

Step 3

Slide the window.

Update hash using:

Remove Left Character

+

Add Right Character

Step 4

If hashes match,

verify character by character.

Optimal Java Solution

class Solution {

    private static final int BASE = 31;
    private static final int MOD = 1000000007;

    public int strStr(String haystack,
                      String needle) {

        int n = haystack.length();
        int m = needle.length();

        if (m == 0)
            return 0;

        long patternHash = 0;
        long textHash = 0;
        long power = 1;

        for (int i = 0; i < m; i++) {

            patternHash =
                (patternHash * BASE +
                 needle.charAt(i)) % MOD;

            textHash =
                (textHash * BASE +
                 haystack.charAt(i)) % MOD;

            if (i < m - 1)
                power = (power * BASE) % MOD;
        }

        for (int i = 0; i <= n - m; i++) {

            if (patternHash == textHash &&
                haystack.substring(i, i + m)
                        .equals(needle)) {

                return i;
            }

            if (i < n - m) {

                textHash =
                    (textHash -
                    haystack.charAt(i) * power % MOD
                    + MOD) % MOD;

                textHash =
                    (textHash * BASE +
                    haystack.charAt(i + m)) % MOD;
            }
        }

        return -1;
    }
}

Dry Run

Input

haystack = "sadbutsad"

needle = "sad"

Pattern Hash:

sad

Window 1:

sad

Hash Matches

↓

Verify

↓

Return 0

Another Example

haystack = "leetcode"

needle = "code"

Windows:

leet

eetc

etco

tcod

code

Hash matches at:

Index = 4

Answer:

Why Rabin-Karp Works?

Instead of comparing every character repeatedly,

we compare only hash values.

When the hash differs:

Strings are definitely different.

When the hash matches:

Verify characters

to avoid collisions.

Complexity Analysis

Metric	Complexity
Average Time Complexity	O(N + M)
Worst Case	O(N × M) (Hash Collisions)
Space Complexity	O(1)

Interview One-Liner

Rabin-Karp uses a rolling hash to compare substrings efficiently, reducing repeated character comparisons during pattern matching.

Pattern Learned

Substring Search

↓

Rolling Hash

↓

Pattern Matching

Memory Trick