A Subquadratic Algorithm for Minimum Palindromic Factorization

We give an $\mathcal{O}(n\log n)$-time, $\mathcal{O}(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S[\mathrm{1..}n]$, in $\mathcal{O}(n\log n)$ time our algorithm returns the minimum number of palindromes $S_1,\dots ,S_{\mathrm{\ell }}$ such that $S = S_1 \cdots S_\ell$\mathrm{.}Wealsoshowthatthetimecomplexityis$$\mathcal{O}$(n)$onaverageand$\Omega(n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.