Two-way string-matching algorithm

ClassString-searching algorithm
Data structureAny string with an ordered alphabet
Worst-case performanceO(n)
Best-case performanceO(n)
Worst-case space complexityO(1)

In computer science, the two-way string-matching algorithm (or Crochemore-Perrin string-matching algorithm) is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. It searches for copies of a "needle" of length m in a "haystack" of length n. After preprocessing the needle in time O(m), the actual search takes time O(n) linear in the length of the haystack.

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 ⌈log2(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(Fc+2 − 1)−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.