Skip to content
Back to AlgorithmsAll lessons

Algorithms

Substring Search

O(n·m) time in the worst case, where n is the text length and m is the pattern length. A near-match can force a full comparison at almost every position · O(1) space. Smarter algorithms like KMP bring this down to O(n + m) time, by never re-checking letters they already matched.

The idea, in plain English

Finding a short word inside a longer piece of text is like sliding a strip of paper with the word written on it along a sentence, one letter at a time. You check whether everything under the strip matches. This is the simplest way to search for a substring, a smaller piece of text inside a bigger one. It is slow, but honest about what it does.

How it works

  1. 1Slide a window the same length as the pattern across the text, one starting position at a time.
  2. 2At each position, compare the window's letters to the pattern's letters, one by one.
  3. 3If every letter matches, record that starting position as a match. Either way, slide the window one step and repeat, until it no longer fits inside the text.

When you'd use it

Use it for simple text search when the text is short to medium in length. It also works as a mental model before you reach for a faster algorithm, like KMP, when the text is huge and speed really matters.

Common beginner mistakes

  • Letting the starting position go too far. It cannot start past text length minus pattern length, or the window runs off the end of the text.
  • Assuming this simple approach is the only way to search text. It is a solid starting point, but real editors and search tools use faster algorithms for long documents.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Text: ababcabab
Pattern: abab
Found at indices: 0 5

See it in motion

Watch it slideSubstring search“issi”O(n·m) time in the worst case, where n is the text length and m is the pattern length. A near-match can force a full comparison at almost every position · O(1) space. Smarter algorithms like KMP bring this down to O(n + m) time, by never re-checking letters they already matched.
Text
m
i
s
s
i
s
s
i
p
p
i
0
1
2
3
4
5
6
7
8
9
10
Pattern
i
s
s
i

Line the pattern up with the start of the text.

Found at
—
0
Comparisons
0
Windows tried
0
Hits
0.0s
Time
ComparingMatched / hitMismatch → shiftWindow

Not sure this is the right topic? See the learning paths → or where this leads →