Two-way string-matching algorithm

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the two-way string-matching algorithm is a <a href="/facts/String-searching_algorithm/RCvwDRle">string-searching algorithm</a>, discovered by <a href="/facts/Maxime_Crochemore/avU0T2fV">Maxime Crochemore</a> and <a href="/facts/Dominique_Perrin/GhEdKeAA">Dominique Perrin</a> in 1991. It takes a pattern of size m, called a “needle”, preprocesses it in linear time <a href="/facts/Landau_notation/weFFjSWg">O</a>(m), producing information that can then be used to search for the needle in any “haystack” string, taking only linear time O(n) with n being the haystack's length.
The two-way algorithm can be viewed as a combination of the forward-going <a href="/facts/Knuth%25E2%2580%2593Morris%25E2%2580%2593Pratt_algorithm/A4uM3D8e">Knuth–Morris–Pratt algorithm</a> (KMP) and the backward-running <a href="/facts/Boyer%25E2%2580%2593Moore_string-search_algorithm/yUGSAvN6">Boyer–Moore string-search algorithm</a> (BM).
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.
Unlike BM and KMP, it uses only <a href="/facts/Landau_notation/weFFjSWg">O</a>(log m) additional space to store information about those partial repeats: the search pattern is split into two parts (its critical factorization), represented only by the position of that split. Being a number less than m, it can be represented in ⌈log₂ m⌉ bits. This is sometimes treated as "close enough to O(1) in practice", as the needle's size is limited by the size of <a href="/facts/Address_space/EscyYKkP">addressable memory</a>; the overhead is a number that can be stored in a single register, and treating it as O(1) is like treating the size of a loop counter as O(1) rather than log of the number of iterations.
The actual matching operation performs at most 2n − m comparisons.
Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle:

<ul><li>The first one performs at most n + ⌊(n − m)/2⌋ comparisons, ⌈(n − m)/2⌉ fewer than the original. It must however store ⌈log<a href="/facts/Golden_ratio/anloSRmD">
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
</a> m⌉ additional offsets in the needle, using O(log2 m) space.</li>
<li>The second adapts it to only store a constant number of such offsets, denoted c, but must perform n + ⌊(1⁄2 + ε) * (n − m)⌋ comparisons, with ε = 1⁄2(<a href="/facts/Fibonacci_number/mqxpAUQD">F</a>c+2 − 1)−1 = O(
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
−c) going to zero exponentially quickly as c increases.</li></ul>
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 <a href="/facts/C_standard_libraries/qdG1nW2c">C standard libraries</a> <a href="/facts/Glibc/AL6IYDkA">glibc</a>, <a href="/facts/Newlib/QSGNXyk9">newlib</a>, and <a href="/facts/Musl/37ByvC8P">musl</a>, to implement the memmem and strstr family of <a href="/facts/C_string_handling/V0AYCYR2">substring functions</a>. As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances; this is especially so if the needle isn't searched in multiple haystacks, which would amortize the preprocessing cost.

Two-way string-matching algorithm open-in-new

Two-way string-matching algorithm