Why str::match_indices Skips Overlapping Matches

I once counted a repeated marker with matches and received fewer occurrences than a visual scan showed. The marker overlapped with itself. In ababa, the substring aba begins at byte zero and again at byte two, but match_indices reports only zero.

The failing program records exactly those expected offsets. Its result is one disjoint match.

A match iterator needs an advancement rule

After finding a substring, a searcher must decide where the next search begins. Advancing to the end of the match produces non-overlapping occurrences. Advancing by one candidate boundary can discover overlaps.

Rust's match_indices and matches follow the non-overlapping policy for string patterns. This matches common splitting and replacement behavior, where consuming the same byte twice would be surprising.

It does not answer every occurrence-start question for self-overlapping patterns.

Overlap depends on the pattern

Patterns such as aba, aaa, and repeated protocol prefixes have proper prefixes that are also suffixes. This structure allows a new occurrence to begin before the current one ends.

For aaaa searched with aa, disjoint matching finds offsets zero and two. Overlapping matching finds zero, one, and two. Neither count is universally correct; the product definition must select one.

Security scanners, sequence analysis, and repeated-delimiter diagnostics often need overlaps. Token replacement and splitting usually need disjoint consumption.

UTF-8 prevents byte-by-byte slicing

The repaired helper cannot blindly try &haystack[index..] for every byte index. A Rust string slice must begin on a UTF-8 character boundary. Slicing inside a multi-byte encoded character panics.

The repaired program obtains candidate starts from char_indices. Each offset is a valid boundary, so starts_with can safely test the needle there. The fixture includes ééé searched for éé, yielding byte offsets zero and two.

The offsets remain bytes, as Rust string indexing APIs document. Two is the second character boundary in that UTF-8 example, not a character count derived from ASCII assumptions.

Empty patterns need their own contract

An empty needle matches at many boundaries under some definitions, and an overlap loop that advances by needle length would never progress. The small repaired helper rejects empty input with an assertion.

Production code should return an error, define all character boundaries as matches, or follow the standard iterator's documented empty-pattern behavior. I make this choice before implementing the loop.

Special cases that decide termination deserve explicit tests rather than a hidden max(1) increment.

Simple scanning and scalable scanning are different

Testing every character boundary with starts_with is easy to read and correct for a small string and needle. Its worst-case work can be much larger than a dedicated linear-time string-search algorithm.

For high-throughput bytes I use an algorithm whose overlap policy is configurable or implement a prefix-function/automaton design. For Unicode text I first decide whether matching means UTF-8 bytes, Unicode scalar values, grapheme clusters, case folding, or normalization. “Substring” alone does not resolve these layers.

I measure with realistic pattern shapes because repetitive data is exactly where naive repeated comparisons can become expensive.

Replacement usually should not overlap

If two matches share bytes, replacing both simultaneously needs a conflict rule. Which replacement owns the shared region? Does the second match see original input or output from the first replacement?

The standard disjoint policy gives deterministic consumption and supports streaming. I do not build overlapping replacement by merely collecting offsets and splicing from left to right. Search semantics and rewrite semantics must be designed together.

Tests should reveal the chosen policy

My table includes no match, one match, adjacent matches, nested overlap, repeated single characters, multi-byte text, empty haystack, and an empty needle policy. I assert offsets rather than only counts because offsets expose skipped internal starts.

For a streaming searcher I test every possible chunk boundary. An occurrence may overlap itself and also cross two input chunks; these are separate state requirements.

The failing ababa example remains useful because five ASCII bytes isolate overlap from every other complication.

The general principle is progress with meaning

Every scanner needs a progress rule after success and failure. Moving farther can be faster and produces disjoint results; moving to the next valid start preserves overlaps. The rule changes the answer, so it belongs in the contract.

Rust's standard string match iterators choose non-overlapping occurrences. I use them when that matches the problem and build an explicit boundary-aware search when every possible start matters.