search

zeusdeux / re2

Automatically exported from code.google.com/p/re2
BSD 3-Clause "New" or "Revised" License
0 stars 0 forks source link

let firstbyte_ to be requiredbyte_ #97

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
DFA use firstbyte_ as anchor for unanchored search.
unfortunately, this could not work on kFBMany which is very common case.
instead of firstbyte_, DFA may use a "MUST" NFA State as anchor.
for example:

regex: [aeiou]+a?Z\d*
[a-z]+ prevent DFA use memchr finding the start anchor, 
so it has to run at every char in match text.
but, "Z" is a "MUST" NFA State, now we use memchr "Z" as anchor, 
run DFA "Z\d*" forward and "[aeiou]+a?Z" backward to find the partial match.

the same may apply to NFA.

Original issue reported on code.google.com by Lyricconch on 29 Oct 2013 at 9:32

GoogleCodeExporter commented 9 years ago 
It's possible but it's too much work. You'd have to scan both backward and 
forward once you found the byte.

Original comment by rsc@golang.org on 10 Jan 2014 at 1:38