[Tim Showalter]:
I implemented a mostly-linear time glob algorithm by implementing
minimal matching left-to-right. I am opposed to any semantic that
would result in pattern matching being fairly expensive
(specifically, any algorithm that results in * being recursive is
bad).
If I had done minimal-matching right-to-left, would the result
have been greedy? (This would resolve my objection.)
yes. just reverse both strings to see this. here's an example:
"ababbab" ~ "*a*b?*" => [ "ab", "b", "a", "b" ] (greedy)
"babbaba" ~ "*?b*a*" => [ "b", "a", "b", "ba" ] (minimal)
or the other pair:
"babbaba" ~ "*?b*a*" => [ "babb", "a", "", "" ] (greedy)
"ababbab" ~ "*a*b?*" => [ "", "", "a", "bbab" ] (minimal)
--
Kjetil T. | read and make up your own mind
| http://www.cactus48.com/truth.html