An interesting question however is: could your non-greedy idea work in general? Consider the case where
pattern = *X*X
input = AXBXCZ
According to the algorithm you described, the first * would match A (the substring until the first X in input). Then the second * would match B (the substring from the previous position to the next X). So we've gone through the entire pattern without encountering any mismatches. Does that mean we can return with "success"? Clearly, *X*X doesn't match AXBXCZ.
I don't think that's the best example as I think his idea would be valid in that it would fail because there is more after the *X*X match unless a * follows that: *X*X*. Using his idea for that example, it would still seem to work properly.
However, here's another example where it would fail.
pattern = *X*X
search = AXBXCX
In this example, his idea is to use * until the first X match, in which case it would be just the A. The second star would match up until the next X, which would be after the B. Because it doesn't have a * after the last X, it would fail because there's more in the search after AXBX. Obviously, it *should* match. Of course, this needs to check in multiple ways (forward and backward)... If the first * included AXB instead of just A, it would match. Or, if the first * was A and the second star included BXC instead of just B, it would also match. That example should help to show why RRX's suggestion won't work.
