The Needle in the Text

You press Ctrl+F, type a word, and it lights up across the page instantly. A biologist searches a genome for a short DNA sequence among billions of letters. A security tool scans network traffic for a known attack signature. All of these are pattern matching: finding where a short pattern appears inside a long text.

The obvious method is to slide the pattern along the text, checking it at every position. It works — but on a long text with a long pattern, it does a lot of repeated, wasted comparisons. For huge inputs, that slowness adds up.

Here's the happy twist, and why this article is a breath of fresh air after the hard problems: pattern matching is solved. Clever algorithms reduced it from slow to linear time — you can scan the whole text essentially once. It's one of computer science's cleanest success stories.

Try it. Type a pattern to find in the text. The demo runs two searches: the naive slide-and-check method and KMP (Knuth–Morris–Pratt), the classic linear-time algorithm. It highlights every match and counts the character comparisons each method makes.

<p class="hint">{{hint}}</p>
<label class="lab">{{lbl_text}}</label>
<textarea id="text" rows="3" class="ta"></textarea>
<div class="row"><label class="lab">{{lbl_pattern}}</label><input id="pat" type="text" value="ana" /><button id="go" type="button">{{btn_search}}</button></div>
<div id="hl" class="hl"></div>
<div class="meters">
  <div class="m"><span>{{naive_cmp}}</span><b id="naive" class="bad">—</b></div>
  <div class="m"><span>{{kmp_cmp}}</span><b id="kmp" class="good">—</b></div>
  <div class="m"><span>{{matches}}</span><b id="hits">—</b></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.lab { font: 600 12px system-ui; color: #777; display: block; margin-bottom: .2rem; }
.ta { width: 100%; font: 600 13px ui-monospace, monospace; padding: .5rem; border: 1px solid #cdd9e2; border-radius: 8px; resize: vertical; }
.row { display: flex; gap: .5rem; align-items: flex-end; margin: .6rem 0; flex-wrap: wrap; }
.row input { font: 700 14px ui-monospace, monospace; padding: .4rem .6rem; border: 1px solid #cdd9e2; border-radius: 7px; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
.hl { font: 600 14px ui-monospace, monospace; line-height: 1.7; background: #f8f9fb; border: 1px solid #e6e9ee; border-radius: 8px; padding: .6rem .8rem; word-break: break-word; min-height: 2.5em; margin-bottom: .8rem; }
.hl mark { background: #ffe08a; color: #7a5a00; border-radius: 3px; padding: 0 1px; }
.meters { display: flex; gap: .7rem; flex-wrap: wrap; }
.m { flex: 1; min-width: 120px; background: #f6f8fa; border: 1px solid #e6e9ee; border-radius: 10px; padding: .5rem .7rem; }
.m span { display: block; font-size: .78rem; color: #777; }
.m b { font: 800 19px ui-monospace, monospace; }
.bad { color: #c0392b; } .good { color: #0a7d33; }

// Code not found

Watch the comparison counts: the naive method redoes work after every near-match, while KMP remembers what it already matched and never backtracks over the text. On repetitive patterns the gap is dramatic — the same answer, far less work. That's a solved problem looking effortless.

This is one of the satisfying easy problems — and a textbook win:

• Checking a match is trivial. Compare the pattern against a slice of text.
• Naive is $O(n \cdot m)$. Sliding a length-m pattern over length-n text and re-checking from scratch wastes effort on near-misses.
• KMP makes it $O(n+m)$. Knuth–Morris–Pratt precomputes a small table from the pattern so that after a partial match it skips ahead without re-reading text it's already seen — a single linear pass.
• Boyer–Moore is often sublinear in practice. By scanning the pattern right-to-left and jumping over big chunks on a mismatch, it can skip most of the text — the algorithm inside many real "find" features.
• Preprocess once, query forever. Suffix trees / arrays and automata index a text so later searches take time proportional only to the pattern, not the text — perfect for search engines and genomics.
• Still active for variants. Exact matching is solved; approximate / fuzzy matching (allowing typos) and regular-expression search keep research lively.

So pattern matching is a story of total victory: a problem that looks like it should cost $O(n \cdot m)$ yields to elegant ideas that make it linear — and often faster.

Fast string search is one of the most-used algorithms on Earth:

• Editors and Ctrl+F: instant find-in-page and find-in-files (grep) across millions of lines.
• Search engines: matching queries against indexed text at web scale.
• Bioinformatics: locating genes and motifs in genomes billions of letters long.
• Intrusion detection and antivirus: scanning traffic and files for known signatures.
• Plagiarism and deduplication: finding shared passages across documents.

Every time you search, the linear-time algorithms (or their indexed cousins) are doing the work in the blink of an eye.

After a tour of problems that are slow, impossible, or quietly NP-hard, pattern matching is a victory lap. The naive idea is wasteful, but a flash of insight — remember what you've already matched and never look back — turns it into a single linear sweep. The needle in the haystack, found in essentially the time it takes to read the haystack once.

It's worth celebrating the wins. Not every problem fights back; some surrender completely to a beautiful idea, and then quietly power the tools we use a thousand times a day. Every Ctrl+F is a tiny monument to an elegant algorithm — proof that, sometimes, "fast and exact" is simply the answer.