Strings — Find the Needle (KMP)

solve(haystack, needle) — return the index of the first occurrence of needle in
haystack, or -1 if it does not occur. An empty needle returns 0. Do not use
indexOf / find / includes.

The naive double loop is O(n · m) on inputs like "aaaa…ab". Knuth–Morris–Pratt gets
O(n + m) by never moving backwards in the haystack. First build the failure table
lps[i]: the length of the longest proper prefix of needle[0..i] that is also a suffix of
it. Then scan the haystack; on a mismatch, instead of restarting, fall back to
lps[matched - 1] and reuse what you already matched.

Examples

solve("sadbutsad", "sad")              → 0
solve("leetcode", "leeto")             → -1
solve("mississippi", "issip")          → 4
solve("aabaaabaaac", "aabaaac")        → 4