Implement strStr

This is the pure string matching problem.

I previously did the shortest palindrome problem in multiple ways. But in a real interview, I think I will just use the RK algo.

Solution

Let $m$ be the length of haystack and $n$ be the length of needle.

Built-in Function

Can use the built-in function find or index in str. Remember to check the empty string.

def strStr(self, haystack: str, needle: str) -> int:
    if needle=="": return 0
    return haystack.find(needle)

RK algo

Pretty standard RK algo. Note the usages of lambda(anonymous function) and ord(returns Unicode code point for a one-character string).

Complexity

time: $O(n)$
space: $O(n)$

def strStr(self, haystack: str, needle: str) -> int:
    h,n = len(haystack),len(needle)
    if h < n:
        return -1

    base = 26
    mod = 10**9 + 7
    hash_h, hash_n = 0, 0

    haystack_to_int = lambda i: ord(haystack[i])-ord('a')
    needle_to_int = lambda i: ord(needle[i])-ord('a')

    for i in range(n):
        hash_n = (base * hash_n + needle_to_int(i)) % mod
        hash_h = (base * hash_h + haystack_to_int(i)) % mod

    # early exit if needle is the prefix of haystack
    if hash_n == hash_h and needle == haystack[:n]:
        return 0

    power = pow(base, n, mod)
    for start in range(1, h-n+1):
        hash_h = (hash_h*base - power * haystack_to_int(start-1) + haystack_to_int(start+n-1)) % mod
        if hash_n == hash_h and needle == haystack[start:start+n]:
            return start
    return -1

KMP (Optional)

Z-algo (REDO)

https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/