The problem. Given two strings haystack and needle, return the index where needle first occurs in haystack, or -1 if it doesn't occur at all. This is indexOf / find — and the question is how to write it yourself.
haystack = "sadbutsad", needle = "sad" -> 0
haystack = "leetcode", needle = "leeto" -> -1
haystack = "abababca", needle = "ababca" -> 2Many string questions come down to where does this pattern occur in this text — or to a fact about how a string's beginning compares to its end. The direct way lines the pattern up at every start and compares letter by letter. That is O(n · m) when there are many near-misses: looking for "aaab" in "aaaaaaaa…" matches three letters at every start before failing.
The Knuth–Morris–Pratt (KMP) algorithm finds the pattern in O(n + m) by never reading a text letter twice. It first studies the pattern on its own and builds a table: lps[i] is the length of the longest border of pattern[0..i] — a proper prefix that is also a suffix. In "abab", the border is "ab". After a mismatch with j letters matched, those j letters are known, and the longest border of them is already a matching start of the pattern. So j drops to lps[j - 1] and the text position stays put.
The table is built the same way, by matching the pattern against itself. When the next letter doesn't extend the current border, the next candidate is the border of that border, lps[len - 1]. The same table answers the next two lessons too: a string with a long border repeats itself, and a border of s + "#" + reverse(s) is a palindrome at the start of s.
In real code, use the built-in indexOf / find — but in an interview, expect to write the direct version first and explain KMP as the follow-up.
function strStr(haystack, needle) { const n = haystack.length, m = needle.length; for (let start = 0; start + m <= n; start++) { let j = 0; while (j < m && haystack[start + j] === needle[j]) j++; // compare letter by letter if (j === m) return start; } return -1;}Time O(n · m), space O(1). Up to n - m + 1 starts, each comparing up to m letters. After a mismatch, the next start forgets everything the last one learned.
Build the border table for the needle, then scan the haystack once without ever moving back.
function strStr(haystack, needle) { const m = needle.length; if (m === 0) return 0; // lps[i]: length of the longest proper prefix of needle[0..i] that is also a suffix of it. const lps = new Array(m).fill(0); for (let i = 1, len = 0; i < m; ) { if (needle[i] === needle[len]) lps[i++] = ++len; // the border grows by one else if (len > 0) len = lps[len - 1]; // fall back to a shorter border else lps[i++] = 0; } // Scan the haystack; after a mismatch, lps says how much of the needle still matches. for (let i = 0, j = 0; i < haystack.length; ) { if (haystack[i] === needle[j]) { i++; j++; if (j === m) return i - m; // all of the needle matched } else if (j > 0) j = lps[j - 1]; // keep the border; i never moves back else i++; } return -1;}Time O(n + m), space O(m). In the scan, every step either moves i forwards (at most n times) or makes j smaller — and j can't shrink more often than it grew, which is only when i moved. The table is built the same way in O(m).
On ordinary text the brute force fails fast and is quick. KMP wins on repetitive inputs — DNA, binary data, or a test case built to be slow — where it stays linear no matter what.
-1 without reading past the end."hello" and "llo": the last start to try is n - m, not n - m - 1."aaaaaaaab" and "aaab": the slow case for brute force.indexOf.lps[j - 1], not lps[j].s + "#" + reverse(s). The lesson after.z[i] = how far the string starting at i matches its own start, with the same uses as KMP.