String Matching

By the end of this lesson you will be able to say exactly what "find the pattern inside the text" means (valid shifts), trace naiveStringMatcher, rabinKarpMatcher (rolling hash, hits and spurious hits), finiteAutomatonMatcher with computeTransitionFunction, and kmpMatcher with computePrefixFunction line by line while a pattern slides over the text cell by cell, implement all of them in idiomatic Dart, see with your own eyes why KMP's nested loop is still linear (an amortized-analysis picture), and choose between them by their real costs (a live comparison table). Interview problems at the end: strStr, repeated substring pattern, shortest palindrome, Z-function, longest duplicate substring and more, each with tested Dart.

0. The problem: text, pattern, shifts

Before any algorithm, we need exact words for the job. A string is just a row of characters, like a row of letter tiles. The long row we search inside is the text t; the short row we look for is the pattern p. Their lengths are n and m (we assume m ≤ n). The characters come from a small fixed set called the alphabet Σ, for example {a, b, c} or the ten digits 0–9. (If you have not met arrays and loops yet, read the lessons on the role of algorithms and insertion and merge sort first; the only extra tool used here is the "big-Θ" running-time notation from growth of functions.)

Pressing Ctrl+F in a document: you type a short word (the pattern) and the editor scans a long page (the text) for every place the word appears. String matching is exactly that scan, and this whole lesson is about doing it faster than "just try every position".
Small example. t = abcab (n = 5), p = ab (m = 2). Print t on graph paper (cells numbered 0, 1, 2, …) and slide a paper strip carrying p along it. With the strip's first cell over cell 0 the strip reads ab against ab: they agree. With the strip moved 1 cell right it reads ab against bc: no. Moved 2 cells: ab vs ca: no. Moved 3 cells: ab vs ab: yes. The strip was slid 0, 1, 2 or 3 cells; the slide amounts that worked are 0 and 3.

Formally the text is an array t[0..n−1] and the pattern an array p[0..m−1], exactly like Dart strings. The pattern occurs with shift s in the text if 0 ≤ s ≤ n − m and t[s..s+m−1] = p[0..m−1]; s is then called a valid shift (in the example the valid shifts are 0 and 3). The task is to find all valid shifts. Two pieces of vocabulary: the k-prefix of p is its first k characters, p[0..k−1] (the 0-prefix is the empty string ε); a string x is a suffix of y when x sits at the end of y, and a prefix when it sits at the start.

Off-by-one traps everywhere: the shift s counts how many cells the pattern has been slid (so it starts at 0), and the window under shift s starts at t[s], not t[s+1]. Every player below shows the 0-based cell numbers above the text, so the shift and the cell under the pattern's first character always read the same number.
The answer can have up to n − m + 1 valid shifts (for t = aaaa…a and p = aa…a every shift is valid), so no algorithm can beat Ω(n − m + 1) in the worst case just to print its answer. The goal is therefore: read the text about once, spend only a little time preparing the pattern, and never repeat a comparison the algorithm has effectively already answered.
The window under shift s is t.substring(s, s + m). All algorithms below assume m ≥ 1 (an empty pattern has no first character to look at); only the naive matcher gives the sensible answer "every shift 0..n" for an empty pattern.

The definition of a valid shift in code:

1. The naive matcher: naiveStringMatcher

The idea is the one you just did by hand: test every one of the n − m + 1 possible shifts, and to test a shift compare the pattern with the window of text underneath it, character by character, stopping at the first difference.

The naive method is the template-sliding picture taken literally: put the paper template at shift 0, compare letter by letter; if everything agrees, write the shift down; slide one cell right and start over. It never remembers anything between shifts, like a person checking a lock with every key on the ring from scratch, forgetting what each key's teeth looked like.
Small example. t = abcab, p = ab. s = 0: a=a, b=b (2 comparisons, valid). s = 1: window "bc": b≠a (1 comparison). s = 2: window "ca": c≠a (1). s = 3: window "ab": a=a, b=b (2, valid). Output: shifts 0 and 3, after 6 character comparisons.

Each shift costs up to m comparisons, so the worst case is Θ((n − m + 1)·m). A text "aaaaaa…a" with a pattern "aaa…ab" is the classic worst case: every window matches almost to the very end before failing on the last character. The info line under each animation counts character comparisons.

Dart implementation (0-indexed; the test t.substring(s, s+m) == p is row 4 of the pseudocode):

Input size → what is feasible. n = 106, m = 5·105 on "aaa…ab" → 2.5·1011 comparisons, hopeless; n ≤ 104, m ≤ 10 or typical English text → fine (most windows fail after 1–2 characters).

The Θ((n − m + 1)·m) worst case and Θ(n − m + 1) best case counted exactly:

If m > n the loop bound n − m is negative, so s <= n - m is false at once and the loop body never runs — correct, since a pattern longer than the text cannot occur (example 2 above). Do not "fix" this with a special case that throws. Also remember that the naive algorithm is a correct baseline: any faster matcher on this page must return exactly the same list of shifts.
Cost picture: in example 3 (all characters equal) every one of the n − m + 1 windows costs m comparisons and every one is a valid shift, so the comparison count equals (n − m + 1)·m exactly. With mismatches early in each window the count drops toward n − m + 1, which is why naive is fine on ordinary English text but not on highly repetitive data. Correctness: the loop tests every s in 0..n−m and the test in row 4 is the definition of "valid shift", so the set reported is exactly the set of valid shifts.
Naive = zero preprocessing, Θ((n − m + 1)m) worst case, O(1) extra space. Its weakness is that after a mismatch it throws away everything the matched characters told it. Every algorithm that follows is a way of not throwing that knowledge away.

2. The Rabin-Karp matcher: rabinKarpMatcher

Idea: compare numbers instead of strings. Read each m-character window as an m-digit number in radix d, reduce it modulo a prime q so it stays small, and only look at the characters when the two small numbers are equal.

Comparing two long words letter by letter is slow; comparing two short fingerprints is fast. Rabin-Karp turns every m-character window into a number (its fingerprint), so "does the window equal p?" becomes "is this number equal to that number?". Equal strings always have equal fingerprints, but different strings can share one by bad luck — that is a spurious hit, and it is why a real character comparison still follows every hit. Think of a coat-check ticket: two coats with the same ticket number must be looked at, but two different tickets prove the coats differ.

Treat each character as a digit in radix d (for digit strings d = 10). Then p[0..m−1] is the number p[0]·dm−1 + … + p[m−1], and Horner's rule (compute a polynomial by repeatedly "multiply by d, add the next digit") computes it in Θ(m). Everything is done mod q for a prime q. The window value at shift s is called ht; sliding one cell to the right costs O(1):

Rolling hash: next ht = ( d·( ht − t[s]·h ) + t[s+m] ) mod q, where h = dm−1 mod q is the weight of the high-order digit. Subtracting t[s]·h deletes the leaving digit, multiplying by d shifts every remaining digit one place up, and adding t[s+m] appends the entering digit.
Small example (d = 10, q = 13, m = 3). h = 10² mod 13 = 100 mod 13 = 9. Window "172" is 172, and 172 mod 13 = 3 (13·13 = 169). Slide one cell so that the leaving digit is 1 and the entering digit is 9 (next window "729"): next = (10·(3 − 1·9) + 9) mod 13 = (10·(−6) + 9) mod 13 = (−51) mod 13 = 1. Check directly: 729 mod 13 = 1 (13·56 = 728). The O(1) update agrees with recomputing from scratch. The pattern 263 used in the first player has hash 263 mod 13 = 3.

In the players below, digits use their own value and lowercase letters a–z use 10–35 (so d = 36 for letter strings); the Dart code uses the same charValue. Rabin-Karp's correctness never depends on this choice, because every hash hit is double-checked with real characters. Watch the info line for the running count of spurious hits (red cells: same hash, different characters).

Dart implementation (the shift s is 0-based already; t[s] is the leaving character, t[s+m] the entering one). Dart's % with a positive modulus is never negative, so no "+ q" fix-up is needed:

Input size → what is feasible. n ≤ 106 with a fixed window length m → n rolling updates ≈ 106 steps, instant; a random prime q ≥ 109 makes spurious hits negligible (n/q ≈ 10−3), but every intermediate product (up to about d2·q in the rolling update) must stay below 263 ≈ 9.2·1018, so d2·q < 9·1018 (d = 256, q = 109 is fine).

Horner's rule and the rolling update: the rolling value must equal the directly computed window value at every shift:

Expected O(n + m): spurious hits ≈ (n − m + 1)/q measured on random digit strings, and the adversarial worst case:

In languages whose % can return a negative number (C, Java, JS) the subtraction in the rolling update can go negative; you must add q back (the page's JS players do exactly that). Another trap: a text of '13' repeated with pattern '00', d = 10, q = 13 makes every "13" window a spurious hit (13 mod 13 = 0), so an adversary who knows q can force Θ(nm) — choose q randomly if inputs are untrusted.
Running time: preprocessing Θ(m); matching Θ((n − m + 1)·m) worst case (for example all windows are valid hits, as in example 2). With v valid shifts and a good q the expected matching time is O(n) + O(m·(v + n/q)): about n/q spurious hits each costing m. With q ≥ m the expected total is O(n + m). Correctness idea: the loop invariant "whenever the hit test runs, ht = the hash of t[s..s+m−1]" is maintained by the rolling update; equal strings always give equal residues, so no valid shift is ever skipped.
Rabin-Karp = Θ(m) preprocessing, O(1) per slide, and a real comparison only on a hash hit. Best when you have many patterns of the same length or a 2-D/duplicate-substring problem; its worst case is still Θ((n − m + 1)m).

3a. Building the automaton: computeTransitionFunction

A finite automaton is a machine with a fixed number of states (boxes), an arrow out of each state for every letter of the alphabet, and one designated start state. Reading a letter means following that arrow. The table that lists "state, letter → next state" is the transition function δ. Our matching automaton for p has states 0..m and its whole design is one sentence: state q means "the last q characters read equal p[0..q−1], and that is the longest such prefix of p".

Think of a combination lock that only cares about progress: it remembers a single number, how many digits of the right code it currently has typed in a row at the end of your key presses. Type a wrong digit and the count does not always fall to zero — if your last few presses still happen to be the start of the code, the lock keeps that much progress. The transition function δ(q, a) answers "I am at progress q and press a: what is my new progress?" — formally the length of the longest prefix of p that is also a suffix of p[0..q−1] + a.
Small example. p = ab, Σ = {a, b}. δ(0, a) = 1 (the 1-prefix "a" is a suffix of "a"); δ(0, b) = 0 ("b" ends with no prefix of p except ε). δ(1, a) = 1 (from "aa" only "a" is a prefix of p); δ(1, b) = 2 (from "ab" the whole p). δ(2, a) = 1 ("aba" ends with the prefix "a"); δ(2, b) = 0 ("abb"). Table: rows q = 0,1,2 → (1,0), (1,2), (1,0).

computeTransitionFunction fills the table straight from that definition: for every state q and every letter a it starts from the largest possible answer and counts down until the k-prefix really is a suffix of p[0..q−1] + a (k = 0 always works). Watch the bottom two rows under each animation frame: the top row is p[0..q−1] + a, the bottom row is the candidate k-prefix right-aligned under it — a suffix test means "does the bottom row match the tail of the top row?". The δ table is drawn under the rows and fills cell by cell.

Dart implementation (states 0..m; the alphabet is a string sigma and δ is a list of rows, one per state, one column per letter of sigma):

Input size → what is feasible. m ≤ 20, |Σ| ≤ 4 → m³|Σ| = 3.2·104, instant; m = 2000, |Σ| = 26 → 2·1011, use the O(m|Σ|) construction (question 15) or KMP instead.

Why the construction is O(m³|Σ|): counting the characters compared; doubling m multiplies the work by about 8:

Why does k start at min(m, q + 1)? The string p[0..q−1] + a has q + 1 characters and a prefix of p cannot be longer than m, so no answer can exceed min(m, q + 1). Starting lower would skip the best candidate and silently produce a smaller δ that misses matches; starting higher is pointless. The loop always stops because k = 0 (the empty prefix) is a suffix of everything. Also, δ is defined for the letters of Σ only; a text letter outside Σ must be handled separately (the Dart matcher below sends the machine to state 0).
Running time: the two outer loops run (m+1)·|Σ| times, the countdown tries up to m+1 values of k, and each suffix test compares up to m characters: O(m³·|Σ|). It is a preprocessing cost paid once per pattern; the prefix function π (next sections) gets the same table in O(m·|Σ|) (interview question on this page) — or avoids storing the table at all.
δ(q, a) = length of the longest prefix of p that is a suffix of p[0..q−1] + a. The table has (m+1)·|Σ| entries, it is filled once, and it never depends on the text.

3b. Running the automaton: finiteAutomatonMatcher

With δ in hand, matching needs no comparisons at all: start in state 0, and for every text character look up the next state. If the state ever equals m, the last m characters read spell the pattern.

A turnstile-style machine turning a crank: read a letter, look up the table, move to the new state. It touches each text character exactly once and never steps backwards. The pattern drawn under the text is the "progress bar" showing the longest prefix of p matched at the tail of what has been read.
Small example. p = ab with the table above, t = aab. Start q = 0. Read t[0] = a: δ(0,a) = 1. Read t[1] = a: δ(1,a) = 1 (the second a restarts progress at 1, it does not reset to 0). Read t[2] = b: δ(1,b) = 2 = m, so a match ends at index 2: shift i − m + 1 = 2 − 2 + 1 = 1.

The state is always the longest prefix of p that is a suffix of the text read so far (Fact C in the checks below), which is why the pattern in the animation appears aligned so that it ends at the character just read, even after a partial mismatch (the machine "falls back" without re-reading anything). Under the text you also see the automaton itself as a state diagram: circles are states, the double circle is the accepting state m, forward arrows carry the pattern's letters, and the curved back-arrows are the fall-backs. Arrows that go to state 0 are left out to keep the picture readable — the highlighted dashed arrow shows one when it is used.

Dart implementation (with the 0-based text index i the match ends at i, so it starts at shift i + 1 − m). A text character that is not in Σ can never extend a match, so it sends the machine to state 0:

Input size → what is feasible. table of (m + 1)·|Σ| ints: m = 104, |Σ| = 26 → 2.6·105 entries, matching n = 107 is exactly 107 lookups; a Unicode alphabet makes the table too big, use KMP.

Three facts about the suffix function σ and the automaton state, verified on every string over {a, b, c} up to length 7:

Two classic slips: (1) forgetting that after a full match the machine is in state m and the table already knows the right continuation (δ(m, a) is defined, so overlapping matches are found with no special code); (2) sizing Σ from the pattern only — a text letter not in Σ makes the table lookup fail, so build Σ from the text too, or guard as the Dart code does.
Running time: matching is Θ(n) — one table lookup per character — after O(m³|Σ|) (or O(m|Σ|) with the faster construction) preprocessing. Correctness idea: by induction on i, the state after reading i characters is σ of the text read so far (Fact C), so q = m exactly when a copy of p has just been read.
Automaton matcher = exactly n table lookups, never backs up, needs an O(m|Σ|) table. KMP (next) keeps the same idea but stores only O(m) numbers.

4a. The prefix function: computePrefixFunction

A border of a string is a proper prefix (shorter than the whole string) that is also a suffix — it appears at both ends. "abab" has border "ab"; "aaa" has borders "aa" and "a"; "abc" has none. The prefix function π[i] is the length of the longest border of p[0..i] (the first i + 1 characters of p).

Suppose you have typed "abaaba" of the pattern "abaabab" and the next letter is wrong. You do not have to start from nothing: the last three typed letters "aba" are also the pattern's first three letters, so you may pretend you have typed just "aba" and continue. π stores, for each prefix, the longest such fallback. For abaabab: π = 0 0 1 1 2 3 2.
Small example. p = abcab. π[0] = 0 always (a single character has no proper prefix). π[1]: "ab" has no border → 0. π[2]: "abc" → 0. π[3]: "abca" has border "a" → 1. π[4]: "abcab" has border "ab" → 2. So π = [0, 0, 0, 1, 2]. Notice how π[4] = 2 was easy to extend from π[3] = 1: the border "a" of "abca" grew to "ab" because the next letter b equals p[1]. That is the whole trick.

The clever part: to compute π you run the same matching idea with the pattern against itself. k is "how many characters of p currently match the tail of p[0..q−1]"; when p[k] does not extend the match to p[q], fall back with k ← π[k−1] — try the next shorter border. Below, the top row is the pattern as text, the second row is the pattern slid so that its first k characters sit under the matched tail, and the bottom row is π filling in step by step; the red pair marks each mismatch that forces a fallback.

Dart implementation. Reading the indices: the loop variable q is the position of the character being added, k is the length of the current border, p[k] is the character that would extend it, and the fallback to the next shorter border is pi[k-1] (the border of the first k characters). Writing pi[k] would read an entry that is not computed yet:

Input size → what is feasible. m ≤ 106 → at most 2(m − 1) = 2·106 comparisons, instant, whatever the pattern.

Three facts about borders and π (the fallback chain and the extension rule) verified on every a/b string up to length 10:

The fallback must be a while, not an if: after one fallback the next shorter border may also fail to extend, and you must keep walking the chain until one extends or k reaches 0 (the interview question "find the bug" has the shortest counterexample, "aaab"). Also, the fallback is pi[k-1] in Dart; writing pi[k] reads the entry that is not computed yet.
Running time Θ(m) (aggregate argument, drawn in the amortized section below): k starts at 0, rises by at most 1 per iteration of the for loop and never goes negative; every pass of the while loop lowers k by at least 1. So the total number of while iterations is at most the total increase, at most m − 1. Correctness idea: at the start of each for iteration k = π[q−1]; the candidates for π[q] are exactly the borders of p[0..q−1] extended by one character, and the chain π[q−1], π[π[q−1]−1], … lists all those borders from longest to shortest (Fact D in the checks above).
π[i] = longest proper prefix of p[0..i] that is also a suffix. Built in Θ(m) by matching p against itself; the fallback chain lists every border from longest to shortest.

4b. The KMP matcher: kmpMatcher

KMP (Knuth-Morris-Pratt) reads the text left to right once, keeping q = "how many characters of p are currently matched". On a mismatch it does not restart; it uses π to keep as much of the match as is still valid.

KMP is the automaton with a sneaky trick: instead of storing a whole table of "where do I go on each letter", store only π and compute the destination on demand by following fallbacks. On a mismatch it slides the pattern right by exactly the amount π says is safe, and the text pointer never moves left — like reading a novel with a ribbon marker you only ever move forward, while a second finger (q) on the pattern hops back a bit when a word does not fit.
Small example. p = aab (π = [0, 1, 0]), t = aabaab. i=0 'a': q 0→1. i=1 'a': p[1]=a matches, q=2. i=2 'b': p[2]=b matches, q=3=m: report shift 2−3+1 = 0, then q = π[2] = 0. i=3 'a': q=1. i=4 'a': q=2. i=5 'b': q=3: report shift 5−3+1 = 3. Shifts [0, 3], with the text index only moving right.

Loop by loop: read t[i]. While the matched count q is positive and p[q] does not equal t[i], fall back with q ← π[q−1]. Then if p[q] now equals t[i], one more character matches. If all m are matched, report the shift and fall back with q ← π[q−1] so overlapping occurrences are found too. The pattern is drawn under the text so that its first q characters sit under the q text characters just matched; the π row under it lights the entry used.

Dart implementation (0-based; the shift of a match that ends at index i is i - m + 1, and pi[q-1] is the border of the q characters matched so far):

Input size → what is feasible. n ≤ 107, m ≤ 106 → at most 2n + 2m ≈ 2.2·107 comparisons, well inside a second; this is the procedure to use when the worst case must be guaranteed.

The reset q ← pi[q−1] after a full match is not optional: without it the next iteration reads p[m], which does not exist. With an empty pattern p[q] also has nothing to read, which is why the Dart code requires a non-empty pattern. Another common slip is falling back to 0 instead of π[q−1], which silently loses overlapping matches ("aaaa" contains "aa" 3 times, not 2).
Running time Θ(n) after Θ(m) preprocessing: same aggregate argument — q rises by at most 1 per text character and every fallback lowers it, so there are at most n fallbacks in total. Compared with the automaton, KMP stores O(m) instead of O(m|Σ|) and gets the same Θ(n) matching. Correctness: KMP simulates finiteAutomatonMatcher: from state q on letter a the automaton goes to q + 1 if p[q] = a, and otherwise to δ(π[q−1], a) — precisely what the while loop computes (checked on every state and letter in the question "KMP simulates the automaton").
KMP = Θ(m) to build π, Θ(n) to match, O(m) memory, never re-reads the text. The nested while loop looks quadratic but is not — the next section draws why.

5. Why KMP is linear: the amortized-analysis picture

A for loop over n characters with a while loop inside it looks like Θ(n²) to a beginner: one character can trigger many fallbacks. Amortized analysis (see the amortized-analysis lesson) bounds the total work over the whole run instead of the worst single step, using a "bank account" called the potential.

A piggy bank. Every text character may drop at most one coin in (q rises by 1 when a character matches). Every fallback takes at least one coin out (π[q−1] < q). You can never take out a coin that is not there (q ≥ 0). So over the whole run the number of coin withdrawals (fallbacks) can never exceed the number of deposits, and deposits are at most n.
Small example. p = aaaab, t = aaaacaaaab. The first four a's deposit four coins (q = 4). The letter c mismatches four times in a row (q: 4→3→2→1→0), so that single character spends 4 fallbacks — expensive! But those four coins were paid in by the four previous characters, and after the burst the account is empty again, so the next characters cost O(1) each. Total: deposits 9, fallbacks 4, comparisons 10 + 4 = 14 ≤ 2n = 20.

In the players below the row of yellow coins under the text is the potential Φ = q; the row labelled "q after each character" records the whole history (green = q went up, red = fallbacks happened, grey = nothing changed); the info line keeps the two tallies R (raises, deposits) and F (fallbacks, withdrawals) with the running check F ≤ R ≤ characters read. The last frame states the amortized bound. The third player applies the same picture to computePrefixFunction (coins = k), and the fourth takes your own text and pattern.

The potential argument as code: raises, fallbacks and comparisons counted on 500 seeded random inputs and on the bursty example of this section:

Do not confuse "one step can be expensive" with "the total is expensive". The bound F ≤ R holds only because every fallback strictly lowers q: π[q−1] < q always. If a fallback could leave q unchanged the argument (and the algorithm) would loop forever.
The accounting in one line. With Φ = q, the amortized cost of iteration i is (1 + fi) + ΔΦi, where fi is its number of fallbacks and ΔΦi ≤ 1 − fi (raise at most 1, each fallback lowers Φ by at least 1). So every iteration's amortized cost is at most 2, the total is at most 2n, and Φ ≥ 0 makes actual ≤ amortized. The very same argument with Φ = k over the q-loop shows computePrefixFunction costs at most 2(m − 1) comparisons.
KMP matching ≤ 2n character comparisons (n + at most n fallbacks) and prefix-function construction ≤ 2(m − 1): total Θ(n + m), independent of how repetitive the strings are. The worst case of naive is the average case of KMP.

6. Comparison: preprocessing and matching times

Now put the four matchers side by side. First the formulas (n = text length, m = pattern length, |Σ| = alphabet size, v = number of valid shifts):

AlgorithmPreprocessingMatchingExtra memory
Naive0O((n − m + 1)m)O(1)
Rabin-KarpΘ(m)O((n − m + 1)m) worst; expected O(n + m) for q ≥ m and few valid shiftsO(1)
Finite automatonO(m³|Σ|) (O(m|Σ|) with the π trick)Θ(n)O(m|Σ|)
KMPΘ(m)Θ(n)O(m)
Choosing a matcher is choosing how to pay: naive pays nothing up front and pays again and again while searching; the automaton pays a big bill up front for the fastest possible search; KMP pays a small bill and gets the same search speed; Rabin-Karp pays a small bill and bets that fingerprints rarely collide.

The table below is computed live by the same algorithms as the players on five inputs (letters use d = 36 and q = 101, digits d = 10 and q = 13). "Naive cmps" counts character pairs compared; "RK" shows the hash updates plus real character comparisons, and how many hits were spurious; "FA" shows the δ-table cells built plus n lookups; "KMP cmps" counts π-construction comparisons plus text comparisons. Every algorithm returns the same shifts (the last column checks it).

These counts are operation counts, not stopwatch times. On real hardware String.indexOf (a tuned library routine) usually beats all four, and the naive scan can be as fast as KMP on ordinary text because most windows fail after 1–2 comparisons. Use the table to see the growth, not to predict milliseconds.
The naive column explodes only on repetitive inputs (row "aaaa…" with pattern "aaaab"), while KMP's stays below 2n + 2m because of the amortized bound of the previous section. The automaton's build cell count is (m+1)|Σ| but each cell costs O(m²) in the direct construction (the O(m³|Σ|) bound); the count shown is cells, not character tests.
Decision rule: single pattern and a guaranteed worst case → KMP; tiny alphabet and you can afford a table (or you are building hardware/regex engines) → automaton; many same-length patterns, 2-D patterns, duplicate-substring problems → Rabin-Karp; short patterns and one-off scans → the library indexOf.

Quiz

Interview questions

Cheat sheet

ProcedurePreprocessingMatching bestMatching average / typicalMatching worstExtra spaceWhen to use
naiveStringMatchernoneΘ(n − m + 1) (first character mismatches everywhere)≈ Θ(n) on random textΘ((n − m + 1)m)O(1)short patterns, one-off searches; the standard library indexOf is usually faster than anything you write
rabinKarpMatcherΘ(m)Θ(n − m + 1) (no hash hits)O(n + m) expected with q ≥ m and O(1) valid shiftsΘ((n − m + 1)m) (all windows hit, or adversarial q)O(1)many patterns of the same length (compare against a hash set), 2D matching, duplicate-substring problems
computeTransitionFunctionO(m³|Σ|) (O(m|Σ|) with the π trick)———O(m|Σ|)builds the automaton table δ
finiteAutomatonMatcheras aboveΘ(n)Θ(n)Θ(n)O(m|Σ|)tiny alphabets, hardware/regex engines, exactly one lookup per character
computePrefixFunctionΘ(m) (at most 2(m − 1) comparisons)———O(m)borders, periods, repeated-substring and palindrome tricks
kmpMatcherΘ(m)Θ(n)Θ(n)Θ(n) (at most 2n comparisons)O(m)worst-case-safe single-pattern search, streaming text (never re-reads input)

Symbols: n = text length, m = pattern length, |Σ| = alphabet size. None of the matchers here is "stable" or "in place" in the sorting sense; all are read-only on the text.