Sliding the pattern across the text
The naive (or brute force) string matching algorithm searches for a pattern of length m inside a text of length n. It tries every possible starting position in the text, and at each position it compares the pattern character by character.
How it works
- Align the pattern at position zero of the text.
- Compare characters left to right until either a mismatch occurs or the whole pattern matches.
- On a mismatch, shift the pattern one position to the right and start the comparison over from the beginning of the pattern.
There is no memory of previous comparisons. Each shift throws away everything learned and restarts.
Cost and intuition
In the worst case, such as a text of all letter a and a pattern of many a followed by a b, almost every position forces a near full scan of the pattern before failing. That makes the comparison count proportional to n times m. On typical text mismatches usually happen quickly, so the average behaviour is far better than the worst case suggests.
Key idea
Naive matching tries every alignment and restarts comparison on each mismatch; it is simple and correct but wastes work because it forgets what earlier comparisons already proved.