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)

Abstract

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
Volume326
Issue number1-3
DOIs
Publication statusPublished - 20 Oct 2004
Externally publishedYes

Keywords

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

Fingerprint

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

Cite this