Introduction

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.

Find It Fast

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">Search the text for a pattern with the <b>naive</b> method and with <b>KMP</b>. Matches are highlighted; the counters show how many character comparisons each method makes.</p>
<label class="lab">text</label>
<textarea id="text" rows="3" class="ta"></textarea>
<div class="row"><label class="lab">pattern</label><input id="pat" type="text" value="ana" /><button id="go" type="button">Search</button></div>
<div id="hl" class="hl"></div>
<div class="meters">
  <div class="m"><span>Naive comparisons</span><b id="naive" class="bad">—</b></div>
  <div class="m"><span>KMP comparisons</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; }

// Pattern matching: naive O(n*m) vs KMP O(n+m). Both find all matches; KMP never re-reads text it already matched, so it does far fewer comparisons.
const DEFAULT = 'banana bandana ananas — a canal: panama. anna and hannah ran.';

function naive(text, pat) {
  const n = text.length, m = pat.length, hits = []; let cmp = 0;
  for (let i = 0; i + m <= n; i++) {
    let j = 0;
    while (j < m) { cmp++; if (text[i + j] !== pat[j]) break; j++; }
    if (j === m) hits.push(i);
  }
  return { cmp, hits };
}
function buildLPS(pat) {
  const m = pat.length, lps = new Array(m).fill(0); let len = 0, i = 1;
  while (i < m) { if (pat[i] === pat[len]) { lps[i++] = ++len; } else if (len) { len = lps[len - 1]; } else { lps[i++] = 0; } }
  return lps;
}
function kmp(text, pat) {
  const n = text.length, m = pat.length, lps = buildLPS(pat), hits = []; let cmp = 0, i = 0, j = 0;
  while (i < n) {
    cmp++;
    if (text[i] === pat[j]) { i++; j++; if (j === m) { hits.push(i - m); j = lps[j - 1]; } }
    else if (j) { j = lps[j - 1]; }
    else { i++; }
  }
  return { cmp, hits };
}

function highlight(text, hits, m) {
  if (!hits.length || !m) return text.replace(/[&<>]/g, c => ({ '&': '&amp;', '<': '&lt;', '>': '&gt;' }[c]));
  const set = new Set(); hits.forEach(h => { for (let k = 0; k < m; k++) set.add(h + k); });
  let out = '', i = 0;
  while (i < text.length) {
    if (set.has(i)) { let j = i; while (j < text.length && set.has(j)) j++; out += '<mark>' + esc(text.slice(i, j)) + '</mark>'; i = j; }
    else { out += esc(text[i]); i++; }
  }
  return out;
}
function esc(s) { return s.replace(/[&<>]/g, c => ({ '&': '&amp;', '<': '&lt;', '>': '&gt;' }[c])); }

function run() {
  const text = document.getElementById('text').value;
  const pat = document.getElementById('pat').value;
  if (!pat) { document.getElementById('hl').textContent = text; return; }
  const a = naive(text, pat), b = kmp(text, pat);
  document.getElementById('hl').innerHTML = highlight(text, b.hits, pat.length);
  document.getElementById('naive').textContent = a.cmp;
  document.getElementById('kmp').textContent = b.cmp;
  document.getElementById('hits').textContent = b.hits.length;
}

document.getElementById('text').value = DEFAULT;
document.getElementById('go').addEventListener('click', run);
document.getElementById('pat').addEventListener('keydown', e => { if (e.key === 'Enter') run(); });
document.getElementById('text').addEventListener('input', run);
document.getElementById('pat').addEventListener('input', run);
run();
Result
Console

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.

The Good News

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⋅m)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)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⋅m)O(n \cdot m) yields to elegant ideas that make it linear — and often faster.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pattern-matching/Content licensed under CC BY-NC 4.0.