Abstract of Paper

Linear-Time Computation of Local Periods
by Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq, Arnaud Lefebvre

Abstract:

We present a linear-time algorithm for computing {\em all} local periods of
a given word. This subsumes (but is substantially more powerful than) the
computation of the (global) period of the word and on the other hand, the
computation of a critical factorization, implied by the Critical
Factorization Theorem.