Periodicity and unbordered words
Tero Harju, Dirk Nowotka · Journal of the ACM · 2007
The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. Consider a finite word w of length n . We call a word bordered if it has a proper prefix, which is also a suffix of that word. Let μ( w ) denote the maximum length of all unbordered factors of w , and let ∂( w ) denote the period of w . Clearly, μ( w ) ≤ ∂( w ). We establish that μ( w ) = ∂( w ), if w has an unbordered prefix of length μ( w ) and n ≥ 2μ( w ) − 1. This bound is tight and solves the stronger version of an old conjecture by Duval [1983]. It follows from this result that, in general, n ≥ 3μ( w ) − 3 implies μ( w ) = ∂( w ), which gives an improved bound for the question raised by Ehrenfeucht and Silberger in 1979.