BEGINNER · 10 MIN · FREE LESSON

Naive string matching

Explore naive string matching through a visual, step-by-step model.

Size 8

Enter {"text":"ababcabcabababd","pattern":"ababd"}. These matching models use printable ASCII; matches are zero-based and may overlap.

default
? comparing
↔ moving
✓ visited
Q queued
✓ done

Find every complete pattern occurrence, including overlaps.

Code language

Speed

1 / 30

Live variables

pattern: ababd
matches

Operation counters

comparisons: 0
swaps: 0
reads: 0
writes: 0

Complexity · O(nm)

best: O(n)
average: O(nm)
worst: O(nm)
space: O(1) auxiliary, excluding output

Compare from each possible alignment; repeated near-matches can redo m comparisons at almost every text position.

n=8

n=16

n=32

105

n=64

231

Measured reads + comparisons, seed 42. Plotted sample sizes respect each lesson’s explicit input limits.

Keyboard: Space play/pause · ←/→ step · R restart · 1–5 speed. Reduced motion disables transitions.

Naive String Matching

Hook

Slide a short stencil across a longer message until every character underneath agrees.

Watch

Try every alignment. Stop at the first mismatch. Use a repeated-character input and compare the resulting counters with a less repetitive example.

How it works

Choose the next possible start index.
Compare pattern characters left to right.
Record a full match and advance by one to allow overlaps.

Try it

Predict a character comparison, run extension, palindrome expansion or merge frequency. Step back and explain which stored state avoided repeated work.

Complexity

O(nm) worst time and O(1) auxiliary space. The player explains the relevant invariant and counts actual comparisons, reads and writes. Output storage is reported separately when it grows with the result.

Code

The four references assume the lesson’s printable ASCII input contract. The foundation Strings lesson separately explains Unicode code points and UTF-16 units. Pattern inputs must be nonempty; text may be empty for matching. Huffman and palindrome inputs must be nonempty.

When to use

Use for short inputs, one-off searches and as a correctness baseline.

Interview pitfalls

Do not skip overlapping occurrences or read beyond the final valid alignment.

Quiz

Check the invariant, cost model and an edge condition below.

MAKE IT STICK

Quick knowledge check

Progress saves on this device and merges with your account after sign-in.

Your notebook

Private lesson notes

0 / 5000 · Saved on this device; synced when signed in.

Loading interactive lesson…

Next: KMP →