◄ WORLD V · SONNY 5DART 113 · a helldive at the net

TWO-WAY MATCHING the matcher inside your C library

Find a pattern in a text in linear time and — unlike KMP or Boyer-Moore — constant extra space (no precomputed table the size of the pattern). It splits the pattern at a “critical position” and scans both directions, using the pattern’s own period to shift. It is the string search compiled into glibc, musl, and newlib — the one your programs actually call.

THE TECHNIQUE critical factorization, then two-way scan

Factor the pattern at its critical position into a left part u and right part v (found from the pattern’s maximal suffixes). At each alignment, scan the right part left-to-right and the left part right-to-left; a mismatch, plus the pattern’s period, tells you exactly how far to shift — with only a handful of integer variables, no table. Search a text. live demo


  






  
HISTORY & CREDIT the algorithm is theirs; the theorem is older

  
“It lives in libc++ std::string::find” — no; that is a naive O(nm) scan. Two-Way is in memmem / strstr (glibc, musl). cited

  

    1970s · the Critical Factorization Theorem (a word’s local period at its critical point equals its global period) is Cesari & Vincent, sharpened by Jean-Pierre Duval — the math engine.

    1991 · Maxime Crochemore & Dominique Perrin publish Two-Way (J. ACM 38(3):651–675) — linear time, constant space, using that factorization. The eponym is correct.

    vs the others · KMP (dart 063) and Boyer-Moore (dart 061) precompute tables of size O(m); Two-Way needs O(1) extra space — which is why C libraries chose it.

    in the wild · glibc memmem/strstr, musl, newlib — billions of substring searches a day.
  

  
The most-run string matcher on Earth, and almost nobody knows its name. Crochemore & Perrin, 1991






  
RECOMMEND FOR I-13 index arithmetic, no auxiliary array

  
Pure index-and-symbol comparisons over arrays, with a handful of scalars — and it finds the match:

  
$ i13 run tw.i13     # pattern GCAGAGAG in the text
match at index 5     # critical position 2, period 7, constant extra space

  

    Recommend: nothing new — encode text and pattern as f64 arrays of code points; the two directional scans are index comparisons; the critical position and the shift are integer arithmetic in a fixed handful of scalars (verified match at index 5). Crucially it needs no auxiliary array — the O(1)-space property survives directly on I-13’s bounded arrays.

    Note: the standing string want (Boyer-Moore-061, KMP-063, BWT-065, LZ78-102) is the only shadow — strings are the aggregate the corpus keeps meeting; here the matching itself needs nothing more.