Find a String in a String | Dataford Interview Questions

The PlayStation Store and PlayStation UI often search text for a requested title or phrase. Implement a substring search function that returns the first index where a pattern appears in a text string, similar to C++ strstr().

Use the Knuth-Morris-Pratt (KMP) algorithm so the text is scanned efficiently without repeatedly comparing characters after a mismatch.

Formal Specification

Given two strings, text and pattern, return the lowest zero-based index at which pattern occurs in text. Return -1 if the pattern does not occur. If pattern is empty, return 0.

The function must be case-sensitive and may use ordinary string indexing, but do not use built-in substring search functions such as find, index, or the in operator for matching.

Constraints

0 <= len(pattern) <= 10^5
0 <= len(text) <= 10^6
Both strings contain printable ASCII characters
Matching is case-sensitive
Return the lowest valid starting index

Function Signature

def find_substring(text, pattern):

Your question is Find a String in a String. 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