Find a pattern inside a text without restarting from scratch after every mismatch, by reusing what the last comparison already told you.
Used for
a, b match; c ≠ a
a b c matches at 2
Pattern "ab" in text "aab". Where does the match start?
Not quite. At position 0, a matches but b meets a. At position 1 the letters a, b match.
Step 1 of 5
Goal: find "abc" inside "ababcab". Slide the pattern along the text and compare letter by letter.
Step 2 of 5
At position 0: a matches, b matches, then c meets a. Mismatch.
Step 3 of 5
The slow way starts over one step later and re-reads letters. Clever methods (KMP and friends) remember that "ab" already matched, so they jump ahead and never re-read the text.
Step 4 of 5
Match found at position 2. The work is about n + m instead of n × m. This family is string matching.
Step 5 of 5
Your turn.
StringsKnuth–Morris–Pratt AlgorithmRabin Karp AlgorithmZ AlgorithmPalindrome CheckHamming DistanceLevenshtein Distance
// Naive O(n * m). KMP, Rabin-Karp and Z do it in O(n + m): see their topics.const indexOf = (text, pat) => { for (let i = 0; i + pat.length <= text.length; i++) if (text.startsWith(pat, i)) return i; return -1;};