I thing that can be defined only once as a library constant:

library StringFinder {
    Vm private constant VM = Vm(Utils.CHEATCODE_ADDRESS);
    
    function contains(string memory subject, string memory search) internal returns (bool) {
        return VM.contains(subject, search);
    }
    
    function startsWith(string memory subject, string memory search) internal pure returns (bool) {
        return VM.indexOf(subject, search) == 0;
    }
    
    // ...
}

This doesn't work on some older versions of Solidity 0.8.x which should be supported for previous versions of OpenZeppelin Contracts.

You could do without the Vm:

return return bytes(subject).length >= bytes(search).length
    && string(bytes(subject).slice(0, bytes(search).length)).equal(search);

Note that it would be pure, without would allow all the previously view function to remain view

We can't use Bytes.slice here because we want to support OpenZeppelin Contracts 4.x and 5.x, and Bytes isn't available in some older versions. We also can't just copy in the Bytes.slice code because older versions of Solidity don't support mcopy.

Same:

return bytes(subject).length >= bytes(search).length
 && string(bytes(subject).slice(bytes(subject).length - bytes(search).length)).equal(search);

Same reasoning as my other comment

Removed the use of vm.contains, similar to the suggestion in count(). This allows this to be pure, and reverted some other functions' mutability to view.

is the contains really needed ?

I'm expecting vm.split(subject, search) to return a string[1] that contains everything when search is not present in subject.

So tokens.length is 1, and tokens.length - 1 is 0

Note that neither this is not a correct implementation of count. It will not return the correct value when the instances overlap. For example, count("aaa", "aa") should return 2

Removed vm.split. Changed function documentation to say that this is for non-overlapping occurrences, as we currently don't have a use case for counting overlaps.