Apostolico-Giancarlo Algorithm

Purpose: A refinement of Boyer-Moore that guarantees at most $2n$ character comparisons in the worst case, versus Boyer-Moore’s $O(nm)$, while keeping its sublinear average behaviour.

The Problem with Boyer-Moore

Plain Boyer-Moore can re-compare the same text characters many times. The classic bad case is pattern aaaa in text aaaaaaaa…: every alignment compares all $m$ characters, giving $\Theta (nm)$. Boyer-Moore-Galil fixes this for the all-occurrences case with a memory trick; Apostolico-Giancarlo fixes it in general.

The Idea

Maintain an array $S$ where $S[i]$ records, for text position $i$, the length of the match that ended there in a previous alignment. Combined with the pattern’s own suffix array of self-overlaps $N[j]$ (the length of the longest common suffix of pattern[0..j] and the whole pattern), this lets a comparison be skipped entirely when the stored information already determines the outcome:

• if $S[i]>N[j]$ → a mismatch is guaranteed; shift immediately;
• if $S[i]<N[j]$ → a match of length $S[i]$ is guaranteed; skip those characters and continue;
• if $S[i]=N[j]$ → the situation is undetermined; resume ordinary character comparison from there.

Each text character is thus either compared or skipped, and the accounting gives the $2n$ bound.

Complexity

• Preprocessing: $O(m+\sigma )$
• Search: $\le 2n$ character comparisons, worst case; sublinear on typical text
• Space: $O(n+m)$ — the $S$ array over the text is the cost of the guarantee

Why it is rarely used

The $O(n)$ extra space is unwelcome for streaming, and in practice the classic Boyer-Moore-Horspool or Sunday simplifications — which drop the good-suffix rule entirely and keep only bad-character skipping — are faster on real text despite their worse theoretical bound. Apostolico-Giancarlo is the answer to “can Boyer-Moore be made worst-case linear without losing its skipping?” rather than a tool anyone reaches for.

The Boyer-Moore family

Variant	Worst case	Extra space	Notes
Boyer-Moore	$O(nm)$	$O(m+\sigma )$	the original
Boyer-Moore-Horspool	$O(nm)$	$O(\sigma )$	bad character only; fastest in practice
Sunday (Quick Search)	$O(nm)$	$O(\sigma )$	looks one past the window
Boyer-Moore-Galil	$O(n)$	$O(m+\sigma )$	linear for all-occurrences reporting
Apostolico-Giancarlo	$\le 2n$ comparisons	$O(n+m)$	general worst-case guarantee
KMP	$O(n+m)$	$O(m)$	never skips, but always linear

Variants / Use Cases

• Theoretical interest — closing the gap between Boyer-Moore’s practice and its theory
• Galil-Seiferas — a different route to linear-time constant-space matching
• KMP or Z-function — what to write when you need a guarantee and short code
• String fundamentals — the periodicity theory both algorithms rest on