Galil-Seiferas Algorithm

Purpose: Exact string matching in $O(n+m)$ time using only $O(1)$ extra space — no failure-function array, no Z-array, nothing proportional to the pattern length.

Why constant space is hard

KMP is linear but stores an $O(m)$ failure function. Boyer-Moore stores $O(m+\sigma )$ tables. Galil-Seiferas (1983) was the first algorithm to achieve linear time with genuinely constant auxiliary space, answering an open question of the era.

The Idea

Everything hinges on periodicity. Decompose the pattern as $P=uv$ where $v$ is “highly periodic” and $u$ is short. Then:

• while scanning, if a mismatch occurs inside the periodic part $v$, the period tells you exactly how far to shift — and the period is a single integer, not a table;
• the non-periodic prefix $u$ is short enough that naive re-scanning of it costs $O(1)$ amortized.

The technical work is in computing this decomposition in $O(m)$ time and $O(1)$ space, which relies on the critical factorisation theorem: every string has a position where the local period equals the global period.

Complexity

• Time: $O(n+m)$
• Space: $O(1)$ — a handful of integer variables
• Comparisons: $\le 5n$ in the original analysis

Related constant-space algorithms

Algorithm	Time	Space	Notes
Galil-Seiferas	$O(n+m)$	$O(1)$	first of its kind, intricate
Crochemore-Perrin (“Two-Way”)	$O(n+m)$	$O(1)$	simpler; this is what glibc memmem and strstr use
Karp-Rabin	$O(n+m)$ expected	$O(1)$	randomised, not worst-case
KMP	$O(n+m)$	$O(m)$	what you write in a contest

The one that actually ships

If you ever need constant-space linear matching in real code, the Two-Way algorithm (Crochemore-Perrin, 1991) is the practical descendant — it is what the GNU C library implements. Galil-Seiferas is the proof of concept; Two-Way is the engineering.

Why it matters conceptually

The critical factorisation theorem and the “periodic tail / short head” decomposition it enables are genuinely useful ideas beyond this algorithm — they underpin the modern theory of runs in strings, Lyndon factorisation, and the linear-time detection of all maximal repetitions.

Variants / Use Cases

• Crochemore-Perrin Two-Way — the practical successor; see Crochemore
• Apostolico-Giancarlo — a different route to worst-case-linear Boyer-Moore
• String fundamentals — periods, borders, and the periodicity lemma
• Memory-constrained matching — embedded systems and streaming, where an $O(m)$ table is not affordable