Linear-time computation of local periods

Jean Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq, Arnaud Lefebvre

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)


We present a linear-time algorithm for computing 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.

Original languageEnglish
Pages (from-to)229-240
Number of pages12
JournalTheoretical Computer Science
Issue number1-3
Publication statusPublished - 20 Oct 2004
Externally publishedYes


  • Algorithm
  • Complexity
  • Local period
  • Period
  • String matching
  • Word


Dive into the research topics of 'Linear-time computation of local periods'. Together they form a unique fingerprint.

Cite this