Dag-Erling Smørgrav <d...@des.no> writes: > Mike Haertel <m...@ducky.net> writes: > > For example if your regex is /foo.*bar/, the initial Boyer-Moore search > > is (probably) searching for foo. > > > > If the initial search succeeds, GNU grep isolates the containing line, > > and then runs the full regex matcher on that line to make sure. > > You don't really need to "isolate the containing line" unless you have > an actual match, do you? There are two cases:
Theoretically no. However, suppose the pattern was /foo.*blah/. The Boyer-Moore search will be for "blah", since that's the longest fixed substring. But verifying a match for the full regexp either requires a regexp matcher with the feature "start here, at THIS point in the middle of the RE and THAT point in the middle of the buffer, and match backwards and forwards", or else running a more standard RE matcher starting from the beginning of the line. So, in practice you pretty much have to at least search backwards for the preceding newline. As you mentioned, you can avoid searching forwards for the next newline if your RE matcher supports using newline as an exit marker. But if the workload characteristics are that matching lines are scarce compared to the input, this is an optimization that just won't matter much either way. _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"
