Substring Search | Dataford Interview Questions

Pocket Gems game clients may need to locate a command or token inside a larger string. Implement a function that returns the starting index of the first occurrence of pattern in text without using built-in substring search functions such as find, index, or regular expressions.

Use the Knuth-Morris-Pratt (KMP) pattern-matching algorithm so repeated characters in the pattern do not cause unnecessary comparisons.

Formal Specification

Given two strings, text and pattern, return the smallest zero-based index i such that text[i:i + len(pattern)] == pattern. Return -1 if the pattern does not occur. An empty pattern is considered to occur at index 0.

Constraints

0 <= len(text) <= 10^6
0 <= len(pattern) <= 10^5
Inputs contain Unicode characters treated as individual Python string characters
Built-in substring search and regular expressions are not allowed
Target complexity is O(len(text) + len(pattern)) time and O(len(pattern)) space

Function Signature

def find_substring(text, pattern):

Your question is Substring Search. 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