Two-way string-matching algorithm

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 ⌈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\leq r(u,v)\leq \mathrm {len} (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 ≥.

The algorithm

This section is missing information about the match function. Please expand the section to include this information. Further details may exist on the talk page. (March 2022)

The algorithm starts by computing a critical factorization of the needle n as the preprocessing step. This step produces the index (starting point) of the periodic right-half, and the period of this stretch. The suffix computation here follows the authors' formulation. It can alternatively be computed using the Duval's algorithm, which is simpler and still linear time but slower in practice.

Shorthand for inversion.
function cmp(a, b)
    if a > b return 1
    if a = b return 0
    if a < b return -1

function maxsuf(n, rev)
    length ← len(n)
    cur_period ← 1       currently known period.
    period_test_idx ← 1  index for period testing, 0 < period_test_idx <= cur_period.
    maxsuf_test_idx ← 0  index for maxsuf testing. greater than maxs.
    maxsuf_idx ← -1      the proposed starting index of maxsuf

    while maxsuf_test_idx + period_test_idx < length
        cmp_val ← cmp(
              n[maxsuf_test_idx + period_test_idx],
              n[maxsuf_idx      + period_test_idx]
        )
        if rev
            cmp_val *= -1
        if cmp_val < 0
            Suffix (maxsuf_test_idx + period_test_idx) is smaller. Period is the entire prefix so far.
            maxsuf_test_idx += period_test_idx
            period_test_idx ← 1
            cur_period ← maxsuf_test_idx - maxsuf_idx
        else if cmp_val == 0
            They are the same - we should go on.
            if period_test_idx == cur_period
                We are done checking this stretch of cur_period. reset period_test_idx.
                maxsuf_test_idx += cur_period
                period_test_idx ← 1
            else
                period_test_idx += 1
        else
            Suffix is larger. Start over from here.
            maxsuf_idx ← maxsuf_test_idx
            maxsuf_test_idx += 1
            cur_period ← 1
            period_test_idx ← 1
   return [maxsuf_idx, cur_period]

function crit_fact(n)
    [idx1, per1] ← maxsuf(n, false)
    [idx2, per2] ← maxsuf(n, true)
    if idx1 > idx2
        return [idx1, per1]
    else
        return [idx2, per2]

The comparison proceeds by first matching for the right-hand-side, and then for the left-hand-side if it matches. Linear-time skipping is done using the period.

function match(needle, haystack)
    needle_len   ← len(needle)
    haystack_len ← len(haystack)
    [length, cur_period] ← crit_fact(needle)
    Matches ← {}                             set of matches.

    Match the suffix.
    Use a library function like memcmp, or write your own loop.
    if needle[0] ... needle[length] == needle[length + 1] ... needle[length + cur_period]
        Matches ← {}
        pos ← 0
        s ← 0

    TODO. At least put the skip in.

References