Naive search
Naive search lines the pattern up at position 0, compares characters left to right until one disagrees or the pattern runs out, and then moves the pattern along by one and starts again. It keeps no table and remembers nothing between attempts, which is both its whole simplicity and its whole cost.
How far it jumps
Move one. Always.
When it is the right choice
For a short pattern in a short text it is genuinely the right choice: it has no precomputation to pay for, it uses no extra memory, and its inner loop is about as cheap as a loop gets. It is also what almost every standard library does for small inputs. What it cannot survive is a text and a pattern that agree for a long way and then disagree — try the repeated-characters scenario and watch the comparison counter against any other page here.
How it works
- Line the pattern up so its first character sits at position i in the text, starting at i = 0.
- Compare the pattern against the text from left to right.
- Stop at the first disagreement, or when the whole pattern has agreed.
- If the whole pattern agreed, record an occurrence starting at i.
- Move to i + 1 and start again, throwing away everything just learned.
Worth noticing
- The skipped counter stays at zero for the whole run. That is not a bug in the counter: naive search never skips a position, and every saving the other five pages make is measured against this number.
- After a mismatch the text pointer moves backwards — back to i + 1, which is usually behind where the comparison failed. Knuth-Morris-Pratt exists precisely to stop that happening.
- On ordinary English it is hard to tell apart from anything else here, because a mismatch usually comes on the first or second character. The degenerate scenarios are where the difference lives.
Cost
- Best
- O(n)
- Average
- O(n + m)
- Worst
- O(n · m)
- Extra space
- O(1)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.