The Boyer-Moore Fast String Searching Algorithm
Interesting, but I’m not sure the algorithm aged well.Memory is a block device now. DDR delivers 8 bytes per transaction per channel, e.g. 16 bytes per transaction for dual-channel memory configuration. Skipping bytes delivers little profit in terms of memory bandwidth (but it saves other things, CPUs have very small limit how many memory load instructions can run per cycle).SIMD instructions can compare vectors for about the same cost as scalars, e.g. _mm_cmpeq_epi8 (SSE2) and vceqq_u8 (NEON) compare 16 bytes with another 16 bytes.If I wanted a super-fast substring search, I would try to leverage these things.