Problem 66 · Strings & Tries

strStr via KMP (and Rabin-Karp)

MediumClassic DSA & systems

01Problem

Return the index of the first occurrence of needle in haystack, or -1. Achieve linear time.

02Key insight

KMP precomputes the longest proper prefix-that-is-also-suffix (LPS) for the needle so mismatches fall back without re-scanning haystack, giving O(n+m) worst case. Rabin-Karp gets expected linear time with a rolling hash and extends to multi-pattern search.

03Solution

solution.pypython44 lines

def build_lps(pattern: str) -> list[int]:
    lps = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps


def str_str(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    lps = build_lps(needle)
    k = 0
    for i, ch in enumerate(haystack):
        while k and ch != needle[k]:
            k = lps[k - 1]
        if ch == needle[k]:
            k += 1
            if k == len(needle):
                return i - k + 1
    return -1


def rabin_karp(haystack: str, needle: str, base: int = 256, mod: int = (1 << 61) - 1) -> int:
    n, m = len(haystack), len(needle)
    if m == 0:
        return 0
    if m > n:
        return -1
    high = pow(base, m - 1, mod)
    target = cur = 0
    for i in range(m):
        target = (target * base + ord(needle[i])) % mod
        cur = (cur * base + ord(haystack[i])) % mod
    for i in range(n - m + 1):
        if cur == target and haystack[i:i + m] == needle:  # verify to rule out collisions
            return i
        if i + m < n:
            cur = ((cur - ord(haystack[i]) * high) * base + ord(haystack[i + m])) % mod
    return -1

Try it first.

TimeO(n + m)

SpaceO(m)

tests.py · 2 passing

tests.pypython3 lines

assert build_lps("aabaaab") == [0, 1, 0, 1, 2, 2, 3]
for h, n in [("sadbutsad", "sad"), ("leetcode", "leeto"), ("aaaaab", "aab"), ("abc", ""), ("a", "ab")]:
    assert str_str(h, n) == rabin_karp(h, n) == h.find(n)

04Staff-level follow-up

Searching thousands of patterns over a log stream? Aho-Corasick (trie + failure links, KMP generalized) gives O(n + total pattern length + matches) in one pass.