Like those two, the 2-way algorithm preprocesses the pattern to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered.
[2] Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle:[3] The algorithm is considered fairly efficient in practice, being cache-friendly and using several operations that can be implemented in well-optimized subroutines.
It is used by the C standard libraries glibc, newlib, and musl, to implement the memmem and strstr family of substring functions.
[4][5][6] As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances;[7] this is especially so if the needle isn't searched in multiple haystacks, which would amortize the preprocessing cost.
It can alternatively be computed using the Duval's algorithm, which is simpler and still linear time but slower in practice.