Problem Statement in English

You’re given two strings, haystack and needle. Return the index of the first occurrence of needle in haystack, or $-1$ if needle is not part of haystack.

Approach

You can just brute force it, but that would be $O(n^2)$ time complexity.

Instead, we’re going to use the Rabin-Karp algorithm to find the first occurrence of needle in haystack in $O(n)$ time complexity.

Since we already know what we want to find, we’re going to maintain a hash of a “window”, so to speak of the same length. As we iterate through the haystack, we will update the hash of the window and compare it to the hash of the needle. If they match, we return the index of the start of the window. If it doesn’t match and the window is the same length as the needle, we will remove the first character from the hash and add the next character to the hash.

But how do we actually maintain this hash? Think of it in terms of bit shifting. When you want to move a bit to the left, you multiply it by $2$. But that’s because $2$ is the base of our number system.

In this case, we will use a base of $256$, since ASCII characters are $8$ bits long. In order to prevent the hash from getting too long we will use a modulo. And modulos play well with prime numbers, so we will use a prime number as our modulo — $257$.

In order to remove the first character from the hash, we subtract the base raised to the power of the length of the needle minus $1$ multiplied by the ASCII value of the first character. That’s essentially like trying to get rid of $2$ in $234$ in a base $10$ number system. You’d subtract $2 * 10^2$ from $234$ to get $34$, where $2$ is the first character, $10$ is the base, and $2$ is the length of the number minus $1$.

If we reach the end of the haystack without finding a match, we return $-1$.

Solution in Python


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        BASE = 257
        MOD = 10**9 + 7

        # construct target hash
        thash = 0
        for char in needle:
            thash = (thash * BASE + ord(char)) % MOD

        # iterate over haystack while maintaining current hash
        l = hash = 0
        nl = len(needle)
        sub = pow(BASE, (nl - 1), MOD)

        for r in range(len(haystack)):
            if r - l + 1 > nl:
                hash -= ord(haystack[l]) * sub
                l += 1
            hash = (hash * BASE + ord(haystack[r])) % MOD

            if hash == thash:
                return l
        return -1

Complexity

  • Time: $O(n)$
    Since we are iterating through the haystack string once, the time complexity is linear with respect to the length of the haystack.

  • Space: $O(1)$
    Since we are using a rolling hash, we only need to store the current hash value and the target hash value, which takes constant space.

Mistakes I Made

I had to look this up :(

And we are done.