# 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)

1
2
3

### # 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

### # Z-algo (REDO)

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