Fuzzy substring matching answers a specific question: does a short query appear somewhere inside a longer text, even when the query has typos or the text spells things differently? The query appl should match Apple Inc., levensthein should match Levenshtein distance, and blu tooth should match Bluetooth adapter. The method is to allow a small number of edits between the query and some contiguous fragment of the target, then to accept the pair when the cheapest such fragment is close enough. The same idea is sometimes called approximate substring matching or fuzzy string search.

This is one specific problem inside the interactive fuzzy matching tutorial, and the word substring is what makes it distinct. The comparison is not between two complete strings, as in ordinary fuzzy matching. It is between the query and the best fragment of the target, and everything outside that fragment is ignored. That one change affects which pairs match, which algorithms are fast, and how the distance should be read.

Fuzzy Substring Matching Finds the Best Window

A window is any contiguous run of characters inside the target. I bought an Apple computer contains windows such as bought, an App, Apple, and le compu. Fuzzy substring matching searches those windows, computes the edit distance between the query and each one, and keeps the cheapest result.

For appl against I bought an Apple computer, the window appl sits at the start of Apple with zero edits. The characters around the window, the space before it and the e after it, are outside the window and cost nothing. The window also does not need to start at the beginning of the target or end at the end. comput appears in the middle of I use a computer daily, with irrelevant characters on both sides.

Why the Window Changes the Answer

Full-string fuzzy matching compares two complete strings. kitten and sitting are compared in full, and the edit distance of 3 covers the entire transformation from one word to the other. Substring matching compares the query with a fragment. The pair appl and Apple Inc. is not a fair whole-string comparison, because most of the second string is context that should not cost anything.

The classic mistake is to run a full-string comparator on the pair anyway. appl against appleinc differs in four trailing characters, so the full-string distance is 4 and the normalized similarity is about 0.5, low enough to reject the pair even though its first four characters match perfectly. Substring matching fixes this by charging nothing for the context around the window.

Preprocessing still matters. Fuzzy matching typically lowercases text and removes spaces and punctuation before comparing, as described in the fuzzy matching tutorial. After lowercasing, appl and Apple Inc. show no difference at all: the apparent p versus P is not an edit, because the comparison never sees the case. In the same way, blu tooth becomes blutooth, so the space never appears as an edit.

The rule to remember: the edit distance is computed between the query and the best-matching substring window, not the entire target.

The Best Window Decides the Distance

The table below evaluates four pairs at a budget of two edits. The best window is the fragment of the normalized target that the query aligns to, and the edit count is the distance to that window only.

Query	Target	Best window	Edits	Match?
appl	Apple Inc.	appl	0	Yes
levensthein	Levenshtein distance	levenshtein	2	Yes*
blu tooth	Bluetooth adapter	bluetooth	1	Yes
qwery	Fuzzy matching	fuzzy	4	No

*The two edits are a substitution pair: the h and t have changed places. A comparator that allows adjacent transposition, Damerau-Levenshtein, charges one operation instead.

The appl example is a prefix hit: the window sits at the start of the normalized target and needs zero edits. levensthein is the swap case. The best window is levenshtein, and plain Levenshtein distance charges two substitutions for the swapped pair, while a transposition-aware comparator charges one, the behavior the hub discusses in its section on transpositions. blu tooth needs one inserted character after the space is removed: bluetooth has an e that blutooth lacks. qwery fails everywhere: even the best window, fuzzy, differs in four positions, so no reasonable budget accepts it.

A normalized similarity score puts the window on the same 0-to-1 scale used for full-string matching:

$$\text{similarity} = 1 - \frac{\text{edit distance to the best window}}{\max(\text{query length}, \text{window length})}$$

The numerator is the cheapest number of repairs between the query and the winning window, and the denominator scales that cost by the longer of the two strings. appl against Apple Inc. scores $1 - 0/4 = 1.0$, and qwery against Fuzzy matching scores $1 - 4/5 = 0.2$. Fuzzy-matching libraries expose exactly this operation: FuzzyWuzzy and RapidFuzz call it partial_ratio, and it works by finding the best window and scoring only that pair.

Watch the Window Search in Action

The widget normalizes both strings, finds the best window with the dynamic-programming scan described below, and renders the result as stacked rows. The top row is the target with the winning window colored and everything else dimmed. A bracket marks the window, and the two alignment lanes below show how each query character lines up with each window character. Emerald columns are exact matches, orange columns are substitutions, blue columns are characters that exist in the target window but not in the query, and red columns are query characters with no target counterpart. The distance and the operation counts appear beneath, and the verdict pill applies the edit budget you select.

The default example, levensthein against Levenshtein distance, needs two substitutions, so with a budget of one edit the verdict is No match. Raise the budget to 2 and the same pair becomes a match: the two orange columns in the alignment are the swapped h and t. This is the budget doing real work, not the strings changing. A comparator that counted adjacent transposition as one operation would accept the pair at a budget of 1, which is why the hub treats transpositions as a separate decision.

Try xyzzy against Fuzzy matching. The best window is fuzzy, which differs from xyzzy in exactly two positions, x becoming f and y becoming u. At a budget of one edit the pair is rejected; at two it is accepted. The same strings sit on both sides of the decision, which shows that the budget is a policy choice, exactly like the thresholds the hub discusses.

The blu tooth preset shows preprocessing in action. The strip reads blutooth because the space is removed, and the single blue column in the alignment is the inserted e that turns the window into bluetooth. The comput preset shows a window in the middle of the target, with dimmed characters on both sides that contribute nothing to the distance.

Sliding Window With Edit Distance

The direct way to find the best window is to slide the query across the target and score every candidate position, keeping the cheapest score. Scoring every window from scratch with full edit distance is wasteful, because adjacent windows share nearly all of their characters. The dynamic-programming formulation computes all windows in a single pass over one table.

The table has one row per target character and one column per query character. The value $dp[i][j]$ is the cheapest edit distance between the first $j$ characters of the query and the best window of the target that ends at position $i$:

$$dp[i][j] = \min\left(dp[i-1][j-1] + \text{cost}(q_j, t_i),; dp[i-1][j] + 1,; dp[i][j-1] + 1\right)$$

with $dp[i][0] = 0$ for every row and $dp[0][j] = j$ for every column. Here $q_j$ is the $j$-th query character, $t_i$ is the $i$-th target character, and $\text{cost}(q_j, t_i)$ is 0 when the characters match and 1 otherwise.

Each boundary and candidate term has a job. The condition $dp[i][0] = 0$ is what lets the window start anywhere: an empty query prefix is satisfied by an empty window at any position, so skipping target characters before the window costs zero. The condition $dp[0][j] = j$ charges for query characters that have no target characters to align with. Inside a cell, the three candidates are continuing a previous alignment with a match or substitution, deleting a target character inside the window, and deleting a query character. The answer is the smallest value in the final column, and tracing back from that cell recovers the window span and the per-character operations, which is exactly what the widget draws.

One pass over the table costs $O(mn)$ time for a query of length $m$ and a target of length $n$. Keeping the full table for traceback costs $O(mn)$ memory; keeping only the current row reduces memory to $O(m)$ when only the distance is needed. For interactive typing against short texts this is instant. When only matches within a budget $k$ matter, the computation can be confined to a band near the diagonal, because cells that imply more than $k$ deleted characters can never be part of an answer. The banded scan costs $O(kn)$, the same cutoff used by Ukkonen’s classic approximate-matching algorithm.

Bit-Parallel Substring Matching

The dynamic-programming scan is simple but still touches every cell. For short queries, bit-parallel algorithms encode the row of the dynamic-programming table as a bit mask and update it with integer operations, processing many cells at once. This is how interactive search boxes stay fast while the query changes on every keystroke.

The enabling observation is that an approximate match behaves like a small automaton. For a query of length $m$ and a budget of $k$ edits, the matching states can be packed into bit vectors, one bit per position. Reading the next target character shifts and masks those bits, which simulates a whole row of scalar cell updates in a handful of integer instructions.

Two algorithms define the family. Simon’s algorithm is the early bit-parallel formulation of Levenshtein distance: it stores the incremental changes of the dynamic-programming row as bit vectors and processes one target character per iteration. Myers’ algorithm is the standard fast implementation used in practice. It encodes each row as a pair of bit vectors that record where the row increases or decreases relative to its predecessor, and updates them with roughly a dozen integer operations per target character. For queries shorter than the machine word, typically 64 bits, the update is constant-time, making a full scan of the target cost $O(n)$ instead of $O(mn)$.

The tradeoff is the same one that limits the automaton view: the bit vectors grow with the query length, and the edit budget is fixed inside the encoding. Bit-parallel methods suit short patterns with a small allowed distance, which is exactly the search-box setting. Fuzzy file finders such as fzf and the VS Code command palette score hundreds of thousands of file paths against a short typed query with bit-parallel substring matching and keep up with every keystroke.

N-Gram Overlap for Larger Texts

Bit-parallel matching still scans the whole target. When the target is a document collection, a codebase, or a database column, even a fast scan is too slow, and indexing wins. N-gram methods break the text into overlapping chunks of $n$ characters, index each chunk, and then retrieve candidate positions where enough chunks overlap the query.

The target fuzzy matching contains the trigrams fuz, uzz, zzy, zym, yma, mat, atc, tch, chi, hin, and ing. The typo maching produces mac, ach, chi, hin, and ing, three of which match the target’s trigrams. That overlap points at the region around matching, and a precise edit-distance check on that region confirms a single substitution. PostgreSQL’s pg_trgm extension builds exactly this kind of trigram index and uses it to retrieve candidate rows before any distance is computed.

The important limit is that trigram overlap is a retrieval step, not a final score. Two strings can share many trigrams and still differ by many edits, and short queries produce so few chunks that the overlap is not discriminating. Production systems use n-grams to narrow the candidate set, then run a window scan on the survivors. This is the same candidate-generation pattern the fuzzy matching tutorial describes for full-string matching.

Setting the Edit Budget

The distance to the best window is a number; the match decision is a choice about how many edits to tolerate. A budget of 0 is exact substring matching, where the query must appear verbatim. A budget of 1 accepts a single typo, and a budget of 2 accepts two typos, a long insertion, or, with a transposition-aware comparator, a swapped pair. The widget makes the choice visible: the alignment and the distance do not move, and only the verdict changes as the budget does.

Budgets are usually small, and products scale them by query length, because two edits in a three-character query mean something different from two edits in a twelve-character query. Elasticsearch’s automatic fuzziness, for example, assigns zero edits to very short terms, one edit to short terms, and two edits to longer ones. The same reasoning applies here: a reasonable budget for appl against a product catalog is smaller than for levensthein against a long document.

The cost of being wrong matters more than the number. Accepting xyzzy as a match for Fuzzy matching at a budget of 2 is harmless in a search box, where the result list is cheap to scan. The same generosity would be dangerous when merging records or matching medication names. The hub’s threshold discussion makes this tradeoff explicit, and the budget here is the substring version of the same decision.

Where Fuzzy Substring Matching Is Used

Search-as-you-type and typo-tolerant search are the most direct uses. A query like blu tooth should retrieve Bluetooth adapter from a product catalog even though the space and the extra letter are in the way. Systems that index text, such as Elasticsearch’s fuzzy query and PostgreSQL’s trigram indexes, are built around retrieving text where the query appears approximately.

Autocomplete is a restricted case: the window is anchored at the start of each candidate, because the reader is completing the beginning of a word. Substring search is the general case, and prefix search is what remains when the window start is fixed at position zero. The two behave differently on the same data, which is why autocomplete and full-text search use different scoring.

Fuzzy file finders such as fzf and editor command palettes match a short typed query against file paths, function names, or settings labels. A few keystrokes must score thousands of candidates per frame, which is why bit-parallel matching and tight budgets are the norm there.

Code and snippet search matches a query against longer bodies of text, where the match can sit in the middle of a line. The window search finds the fragment, and the surrounding code provides context for the reader.

Common Mistakes

• Comparing the query to the whole target. The distance must be taken against the best window; otherwise context inflates the cost and real matches are rejected, as with appl against Apple Inc..
• Skipping normalization. Case and spacing become fake edits. blu tooth then needs an extra substitution for the space, and Apple Inc. shows a case difference that should never have been counted.
• Treating the budget as a fixed constant. One or two edits is typical for short queries, but the right number depends on query length and on the cost of a wrong acceptance. The same pair can be a match at a budget of 2 and a miss at 1.
• Using n-gram overlap as the final score. Overlap retrieves candidates; edit distance decides. Two strings can share many trigrams and still need many edits.
• Assuming the window starts at the beginning. Containment search scans all windows. Prefix matching, as in autocomplete, is the special case where the window start is fixed, and the two behave differently on the same data.

Summary

Fuzzy substring matching decides whether a query appears inside longer text by finding the cheapest contiguous window of the target, counting the edits between the query and that window, and comparing the count with a budget. The window can start and end anywhere; characters outside it never contribute to the distance. The sliding-window dynamic program computes all windows in one $O(mn)$ pass, bit-parallel methods make short-query searches interactive, and n-gram indexes make the search practical over large collections.

The decision layer is the same one the fuzzy matching tutorial teaches for full-string matching: normalize the text, choose a comparator, and set the budget according to the cost of being wrong. For the surrounding algorithm landscape, see Fuzzy String Matching Algorithms Explained for the comparator families, Fuzzy Search vs Fuzzy Matching for how this operation becomes a retrieval system, and What Is Fuzzy Matching? for the basic concept. If you want to see how search engines keep these scans fast over large dictionaries, How Typo Tolerant Search Finds Fuzzy Matches Fast walks through the trie automaton used for pruning.