1. Find the Index of the First Occurrence in a String (LeetCode)
Model answer
The task
Given a text string and a pattern string, return the starting index of the pattern’s first occurrence in the text. Return -1 if it does not occur; an empty pattern matches at index 0.
Key idea
Use Knuth–Morris–Pratt (KMP). Its prefix table lets the search reuse information about matched characters instead of restarting from scratch after a mismatch.
Approach
- Build a prefix table for the pattern. At each position, it records the length of the longest proper prefix that is also a suffix.
- Scan the text while tracking how many pattern characters currently match.
- On a mismatch, use the prefix table to find the next viable match length.
- Return the match’s starting index when the entire pattern matches; otherwise return
-1.
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
# Build the longest-prefix-suffix table for needle.
lps = [0] * len(needle)
prefix_len = 0
i = 1
while i < len(needle):
if needle[i] == needle[prefix_len]:
prefix_len += 1
lps[i] = prefix_len
i += 1
elif prefix_len > 0:
prefix_len = lps[prefix_len - 1]
else:
i += 1
# Search haystack without rechecking matched characters.
text_i = 0
pattern_i = 0
while text_i < len(haystack):
if haystack[text_i] == needle[pattern_i]:
text_i += 1
pattern_i += 1
if pattern_i == len(needle):
return text_i - pattern_i
elif pattern_i > 0:
pattern_i = lps[pattern_i - 1]
else:
text_i += 1
return -1
Complexity:
- Time: O(n + m), where
nandmare the text and pattern lengths. - Space: O(m), for the prefix table.
Common follow-ups
- How would you handle many pattern searches in the same text? Build an index or use a multi-pattern algorithm such as Aho–Corasick.
- What if the text arrives as a stream? Keep the KMP match state and prefix table between chunks.
- How would you find all occurrences? After each full match, record its start and reset the pattern index using the final prefix-table value.