How would you find a given string in a longer string, and what is its asymptotic complexity?
Asked in the First Technical Phone Screen, France interviewer, 30 min. Implement substring search using an efficient algorithm and return the starting index of the first match.
Implement substring_search(text, pattern). Return the zero-based starting index, or -1 if the pattern does not occur. Return 0 when pattern is empty.
def substring_search(text, pattern):