Skip to interview prep
Apexed

317. How does brute-force string matching work, and what is its complexity?

EasyString algorithms

Technical
Show model answer

For each shift i from 0 to n − m, compare the pattern with the text starting at i character by character, stopping at the first mismatch. The worst case is O((n − m + 1)·m) ≈ O(nm), for example a text of all “a” and a pattern “aaa…ab”. It needs no preprocessing and O(1) extra space.

On typical natural-language text, mismatches occur early, so the average is close to O(n), which is why simple implementations remain common for short patterns. Algorithms like KMP and Boyer-Moore avoid re-examining characters to guarantee better bounds.

How does brute-force string matching work, and what is its complexity — Data structures & algorithms interview question — Apexed