Find the First Occurrence (KMP)
Medium · Arrays & Strings · about 25 minutes
Asked at Google, Microsoft, Apple.
Search for the pattern needle inside the text haystack and report where its first match begins (a 0-based position), or -1 when it never appears. An empty needle is found at position 0. Target O(n + m) time using Knuth–Morris–Pratt.