Two-way string-matching algorithm

The two-way string-matching algorithm, also called the 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 short needle of length m inside a longer haystack of length n. After preprocessing the needle in time proportional to m, the search itself takes time linear in the length of the haystack. It can be viewed as a combination of the forward-going Knuth-Morris-Pratt algorithm and the backward-running Boyer-Moore algorithm: like them it preprocesses the needle to find partially repeating periods and uses them to compute shifts, but unlike them it needs only constant additional space for that information. The preprocessing computes the period of the needle and a critical factorization of it into a prefix and a suffix, and the matching phase performs at most 2n minus m comparisons. Breslauer later published two variants that make fewer comparisons at the cost of storing extra offsets. The algorithm is cache-friendly and is used by the C standard libraries glibc, newlib and musl to implement the memmem and strstr family of functions.