Standard Bar Strings Hard · Hard O(m + n) · O(m)
A parcel line prints a long serial tape, and customs looks for one short tag code anywhere along it. The scanner must report where the tag first appears, or flag absence. Brute-force re-scanning stalls on adversarial tapes, so the reader uses a prefix-failure table to slide forward without re-checking matched characters.
Input: Two strings: haystack (the tape) and needle (the tag).
Output: Return the 0-based position where the tag first shows up on the tape, or -1 when the tape never contains it. An empty tag matches at position 0.
0 <= len(haystack), len(needle) <= 5 * 10^4strings consist of lowercase or uppercase English lettersInput: {"haystack":"sadbutsad","needle":"sad"}
Output: 0
The tag appears at index 0 (and again at 6); the first hit wins.
Input: {"haystack":"leetcode","needle":"leeto"}
Output: -1
The tag never shows up on the tape.