You can write an NFA implementation that can inspect each byte once. Of course, you won't get capturing or greedy/non-greedy semantics as a result. Even Start o

You can write an NFA implementation that can inspect each byte once. Of course, you won't get capturing or greedy/non-greedy semantics as a result. Even Start of Match is a challenge. We did have a project for a while which did capturing (in a Glushkov NFA) in two passes - you had to inspect each byte twice (if you were content with a O(N) size requirement for side storage, where N is the size of the input), three times (with a O(sqrt(N) side storage requirement), ... k times (with a O(power(N, 1/(k-1)) side storage requirement). It was quite cool, but we never found a customer, and it polluted the Hyperscan source base in many weird ways.