Hints — p93 Implement strStr / KMP

1. Naive O(n·m) is the baseline. KMP gets O(n+m) by never restarting i in the haystack.

2. Precompute lps (longest proper prefix-suffix): lps[i] = length of longest proper prefix of needle[0..i] that’s also a suffix.

3. Building lps: maintain length = previous longest. On match, length += 1, lps[i] = length, i++. On mismatch, fall back via length = lps[length-1] (without advancing i), unless length == 0 (then lps[i] = 0, i++).

4. Match loop: walk i through haystack and j through needle. On mismatch with j > 0, set j = lps[j-1]; else i++. On j == m, found match at i - m.

5. Amortized linear: i strictly increases; j increases at most n times, decreases at most n times. Total O(n+m).

If stuck: see solution.py.