# 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

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

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

base = 26
mod = 1000000007
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
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
``````

### # Z-algo

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

Last Updated: 7/19/2020, 3:45:14 PM