leftmost_find_iter_from_iter_from?

[Gowee]

Hi!

Would it be possible add leftmost_find_iter_from_iter_from in the future? Is it just not implemented yet or technically infeasible?

[vbkaisetsu]

Technical reasons.
While the standard match can accept an iterator, the left-most match must accept a seekable array.

Here is an example:

patterns: ["abbabbb", "abb"]
haystack: "abbabba"
indices:   0123456

The overlapping match works as follows:

0
1
2 <- Outputs [0..3] (abb)
3
4
5 <- Outputs [3..6] (abb)
6
EOS

The left-most match works as follows:

0
1
2 <- Updates output candidate [0..3] (abb)
3
4
5
6 <- Fails. Outputs [0..3], resets the automaton, and seeks to idx=3 (Most recent successful match position)
3
4
5 <- Update output candidate [3..6] (abb)
6
EOS <- Outputs [3..6]

In this paper, the left-most longest match works without seeking the given haystack, but each state must have a variable-length array.
Daachorse represents each state in the space of only 12 bytes for cache efficiency, so we don't want to increase in capacity.