Crochemore Algorithm

Purpose: Maxime Crochemore’s name attaches to several string algorithms. The two that matter are:

1. the Two-Way algorithm (Crochemore-Perrin, 1991) — exact matching in $O(n+m)$ time and $O(1)$ space;
2. Crochemore’s repetitions algorithm (1981) — find all maximal repetitions (squares/runs) in $O(n\log n)$.

---

Two-Way Algorithm

The practical answer to constant-space linear-time matching, and the algorithm implemented by glibc’s strstr and memmem.

The Idea

Use the critical factorisation theorem: every string $P$ has a position $\ell$ splitting it into $P=P_{\text{left}}{P}_{\text{right}}$ where the local period at $\ell$ equals the global period $p$ of $P$. Such an $\ell$ can be found in $O(m)$ time and $O(1)$ space by computing the maximal suffix of $P$ under both the normal and reversed alphabet orders and taking the better one.

Then match in two directions from that split point:

1. Scan $P_{\text{right}}$ left to right. On a mismatch at offset $j$, shift by $j+1$ — no table needed.
2. If the right part matches fully, scan $P_{\text{left}}$ right to left. On a mismatch, shift by the period $p$.
3. Remember how much of the left part was verified (a single integer of “memory”) so characters are never re-compared.

Complexity

• Preprocessing: $O(m)$ time, $O(1)$ space
• Search: $O(n)$, at most $2n-m$ comparisons
• Space: $O(1)$

This is strictly better than KMP on space and competitive on time, which is why it won the libc slot.

---

Repetitions Algorithm

Finds all maximal repetitions (runs) — maximal substrings $w$ with period $p\le |w|/2$ — in $O(n\log n)$.

The Idea

Iteratively refine an equivalence-class partition of positions by the substring of length $2^k$ starting there, doubling $k$ each round (the same partition-refinement idea as prefix doubling for suffix arrays, and closely related to Hopcroft’s DFA minimisation). Classes with two positions at distance $\le 2^k$ reveal repetitions.

Modern alternative: the runs theorem (Bannai et al., 2015) shows a string of length $n$ has fewer than $n$ runs, all findable in $O(n)$ via Lyndon roots and a suffix structure.

Variants / Use Cases

• Galil-Seiferas — the earlier, more intricate constant-space algorithm Two-Way replaced
• KMP — the contest default; simpler, $O(m)$ space
• Main-Lorentz algorithm — $O(n\log n)$ divide and conquer for all squares, easier to implement than Crochemore’s
• String fundamentals — periods, borders, critical factorisation
• Data compression — detecting repetitions is the core of LZ-family compressors