A finite word w is called rich if it contains vertical bar w vertical bar +1 distinct palindromic factors including the empty word. For every finite rich word w there are distinct nonempty palindromes w(1), w(2), ..., w(p) such that w = w(p)w(p-1) ... w(1) and w(i) is the longest palindromic suffix of w(p)w(p-1) ... w(i), where 1 <= i <= p. This palindromic factorization is called UPS-factorization. Let luf(w) = p be the length of UPS-factorization of w. In 2017, it was proved that there is a constant c such that if w is a finite rich word and n = vertical bar w vertical bar then luf(w) <= cn/ln n . We improve this result as follows: There are positive constants mu, kappa such that if w is a finite rich word and n = vertical bar w vertical bar then luf(w) <= mu/e(kappa)root ln n. The constants c, mu, kappa depend on the size of the alphabet. (C) 2022 Elsevier B.V. All rights reserved.
NSTL
Elsevier
