I must have missed that part of the problem description. The first version should work fine without the anchors.

There is a problem with removing the anchors however (and not just in my solution, I think). It would be possible to find a match with fuzzies while there's an exact match later on in the string.