As mentioned in PR #14068 it has been on my mind for sometime to add a few handy string search functions to the String module.

In this gist I have implemented primitives for string searching with both naive string search and the two way algorithm¹ and functions that I'd like to see in String.

A toy benchmark that compares both algorithms seems to indicates that we could simply go with this without special casing small needles (at least as far as I'm concerned, it seems to show good all round behaviour). If you have hyperfine and ocamlopt in your PATH you can try it with:

git clone https://gist.github.com/e395cad463b41db96c74b94af79c81c6.git strstr
cd strstr
./bench.sh 
./bench.sh --search-first  # Single match
./bench.sh --worst-case    # Watch naive search being naive

If there is interest in upstreaming I think a strategy could be to start with [r]find_sub and the underlying primitives and then make other PRs to bikeshed the other functions. However while I have a good idea on how the algorithm works now there remains one or two index computations that I cargo culted that I'd prefer to fully absorb before – but I won't bother if upstream is not interested.