Unit tests are supposed to enable you to safely refactor or rewrite code, because the tests guarantees you don't break anything. But if the test is coupled to the implementation, you will have to modify the test at the same time as the code, which means you could easily introduce errors, and the whole benefit of unit tests is lost.
In short, unit tests should verify that the unit fulfills its requirements, but not how it does this, which is is the implementation details.
This is why it is bad practice to test private methods. Private methods are supposed to be implementation details. The same goes for verifying if a private method is called or not.
In your case, the expected behavior is the specification of the match. Whether this is implemented in one or more methods is an implementation detail. Imagine you find a better fuzzy matching algorithm which have the property that is as fast as a regular string match when there is a direct match. This allows you to skip the special casing of the exact match. This would be an improvement which preserved the expected behavior - but it would cause your test to fail!
But I understand you want to ensure the performance optimization is not lost. There are two possibilities:
- the performance benefit for this optimization is insignificant
- the performance benefit is significant
In case the benefit is insignificant, you should not waste time on testing it. If it is significant you should test it, but you should test the actual performance not just whether certain methods are called or not.