Given a string $s$ of length $n$ over a general alphabet and an integer $k$, the problem is to decide whether $s$ is a concatenation of $k$ nonempty palindromes. Two previously known solutions for this problem work in time $O(kn)$ and $O(n\log n)$ respectively. Here we settle the complexity of this problem in the word-RAM model, presenting an $O(n)$-time online deciding algorithm. The algorithm simultaneously finds the minimum odd number of factors and the minimum even number of factors in a factorization of a string into nonempty palindromes. We also demonstrate how to get an explicit factorization of $s$ into $k$ palindromes with an $O(n)$-time offline postprocessing.

Palindromic length of a string is the minimum number of palindromes whose concatenation is equal to this string. The problem of finding the palindromic length drew some attention, and a few O(n log n) time online algorithms were recently designed for it. In this paper we present the first linear time online algorithm for this problem.

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation, Θ(n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞Ε(n,k)/n does not exist for any k ≥ 2, liminfn→∞Ε(n,k)/n=Θ(1), and limsupn→∞Ε(n,k)/n=Θ(k ). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.