First Occurrence of Substring | Dataford Interview Questions

TomTom navigation software may need to locate the first occurrence of a search phrase within a route instruction or map label. Given two strings, haystack and needle, return the index of the first character where needle occurs in haystack.

If needle does not occur, return -1. If needle is empty, return 0.

Formal Specification

Implement str_str(haystack, needle):

Input: Two strings, haystack and needle.
Output: An integer representing the starting index of the first occurrence of needle in haystack, or -1 if no occurrence exists.
Matching is case-sensitive, and characters must match contiguously.

For the target complexity, preprocess needle using the Knuth-Morris-Pratt algorithm rather than restarting comparisons after every mismatch.

Constraints

0 <= len(haystack) <= 10^5
0 <= len(needle) <= 10^4
Both strings contain printable ASCII characters
Matching is case-sensitive
The target complexity is O(len(haystack) + len(needle)) time

Function Signature

def str_str(haystack, needle):

Your question is First Occurrence of Substring. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem