Skip to interview prep
Apexed

70. Find a Substring (KMP)

MediumString algorithms

Return the index of the first occurrence of needle in haystack, or -1. Do not use built-in search methods; aim for O(n + m).

Example 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

Constraints

  • 1 ≤ haystack.length, needle.length ≤ 10⁴

Tab indents · Ctrl/⌘ + Enter runs · Esc then Tab leaves the editor

Run checks these cases; the expected output comes from the reference solution. Submit judges all 4 hidden and sample tests.

Code runs only in your browser in an isolated sandbox. Progress and submissions are saved on this device.

Find a Substring (KMP) — coding interview practice — Apexed