Implementation: naive search

Implement the naive search and return the first index or -1.

Where used

Reference implementation for benchmarking against JDK and KMP. Useful to justify optimizations rather than guess.

Depth

A direct implementation uses an outer loop over starting positions and an inner loop over pattern characters. The invariant of the inner loop is: before comparison j, the first j pattern characters match the text segment.

If j equals the pattern length, a complete match has been found. The empty search string can consistently be considered at position zero. If the pattern is longer than the text, there is no valid alignment and the outer loop will not be entered.

Difficulty levels

1. Set loop bounds for text and pattern length.
2. Use the inner loop invariant for correctness.
3. Collect all matches including overlaps.

Pitfalls

The expression text[i + j] requires the safety guaranteed by the outer boundary. A break at the first unequal character should not accidentally terminate the entire search instead of just the current alignment.