Periods and binary words



: Halava V, Harju T, Ilie L

Publisher: ACADEMIC PRESS INC

: 2000

Journal of Combinatorial Theory, Series A

JOURNAL OF COMBINATORIAL THEORY SERIES A

: J COMB THEORY A

: 89

: 2

: 298

: 303

: 6

: 0097-3165

DOI: https://doi.org/10.1006/jcta.1999.3014


We give an elementary short proof for a well known theorem of Guibas and Odlyzko stating that thr sets of periods of words are independent of the alphabet size. As a consequence of our constructive proof, we obtain a linear time algorithm which, given a word, computes a binary one with the same periods. We give also a very short proof for the famous Fine Wilf periodicity lemma. (C) 2000 Academic Press.



Last updated on 2025-13-10 at 14:07