HashChain

Ah, last weekend I was just updating my own string search algorithm to use Bitap (Shift-OR variant) instead of KMP, when the pattern length is < 64. It is faster. It is a very lovely algorithm indeed. My search algorithm, HashChain [1] is a very fast sublinear algorithm, but is uses KMP (and now Bitap) to verify matches so it has a linear worst case (instead of quadratic, like Boyer Moore Horspool). [1] https://github.com/nishihatapalmer/HashChain

Looks nice! One little thing I spotted is you use Boyer Moore Horspool for fast literal search. This is actually not linear in the worst case, although it is almost always sublinear. Worst case would be a literal composed of the same character searching a text of the same character, where it becomes quadratic. You can actually search strings with character classes using Horspool if you want to, and I have some enhancements to basic Horspool which could maybe help. My library, byteseek [1], implements these. I also have a much faster algorithm, HashChain [2] which also has a guaranteed linear time version. This was published in the Symposium for Experimental Algorithmics in 2024. [1] https://github.com/nishihatapalmer/byteseek [2] https://github.com/nishihatapalmer/HashChain

May be true for offline full text search, but not true for online string search. I invented a very fast string search algorithm based on bloom filters. Our paper [1] was accepted to the Symposium of Experimental Algorithms 2024 [2]. Code can be found here [3]. [1] https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.S... [2] https://sea2024.univie.ac.at/accepted-papers/ [3] https://github.com/nishihatapalmer/HashChain

Interesting. You may be interested in a more modern search algorithm to replace Boyer Moore. I recently presented HashChain, a very fast sublinear search algorithm at the Symposium of Experimental Algorithms. https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea... It's the fastest sublinear search algorithm around in almost all cases. I also have a guaranteed worst-case linear version (which is still sublinear and much faster than Boyer Moore in the average case). Sample code is available here: https://github.com/nishihatapalmer/HashChain If you're interested, let me know.