Two-way string-matching algorithm

The two-way algorithm can be viewed as a combination of the forward-going Knuth–Morris–Pratt algorithm (KMP) and the backward-running Boyer–Moore string-search algorithm (BM). Like those two, the two-way algorithm preprocesses the needle 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 O(1) additional space to store information about those partial repeats (assuming the transdichotomous model, where an index of ⌈log₂(m)⌉ bits is counted as a single word). The preprocessing computes the "period" of the needle, the minimum offset between two consecutive matches (a value between 1 and m), and a "critical factorization" of the needle into a prefix and suffix with particular properties, specified by the length of the prefix (also less than m).

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:

• The first one performs at most n + ⌊(n − m)/2⌋ comparisons, ⌈(n − m)/2⌉ fewer than the original. It must however store ⌈log_φ m⌉ additional offsets into the needle.
• 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(F_c+2 − 1)⁻¹ ∈ O(φ^−c) going to zero exponentially quickly as c increases.

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. 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.

Critical factorization

Before we define critical factorization, we should define:

• A factorization is a partition ⁠${\displaystyle (u,v)}$⁠ of a string x. For example, ("Wiki","pedia") is a factorization of "Wikipedia".
• A period of a string x is an integer p such that all characters p-distance apart are equal. More precisely, x[i] = x[i + p] holds for any integer 0 < i ≤ len(x) − p. This definition is allowed to be vacuously true, so that any word of length n has a period of n. To illustrate, the 8-letter word "educated" has period 6 in addition to the trivial periods of 8 and above. The minimum period of x is denoted as ⁠${\displaystyle p(x)}$⁠.
• A repetition w in ⁠${\displaystyle (u,v)}$⁠ is a non-empty string such that:
  • w is a suffix of u or u is a suffix of w;
  • w is a prefix of v or v is a prefix of w;

  In other words, w occurs on both sides of the cut with a possible overflow on either side. Examples include "an" for ("ban","ana") and "voca" for ("a","vocado"). Each factorization trivially has at least one repetition: the string vu.

• A local period is the length of a repetition in ⁠${\displaystyle (u,v)}$⁠. The smallest local period in ⁠${\displaystyle (u,v)}$⁠ is denoted as ⁠${\displaystyle r(u,v)}$⁠. Because the trivial repetition vu is guaranteed to exist and has the same length as x, we see that ⁠${\displaystyle 1\le r(u,v)\le \mathrm{l}\mathrm{e}\mathrm{n}(x)}$⁠.

Finally, a critical factorization is a factorization ⁠${\displaystyle (u,v)}$⁠ of x such that ⁠${\displaystyle r(u,v)=p(x)}$⁠. The existence of a critical factorization is provably guaranteed. For a needle of length m in an ordered alphabet, it can be computed in 2m comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.