A Subquadratic Algorithm for Minimum Palindromic Factorization

Abstract

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_{\ell }$ such that $S=S_1\cdots S_{\ell }$. We also show that the time complexity is $\mathcal{O}(n)$ on average and $\Omega (n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

Accepted for publication in Journal of Discrete Algorithms

References in corpus (1)

• ${\mathrm{Pal}}^k$ Is Linear Recognizable Online

Cited by in corpus (15)

• Diverse Palindromic Factorization is NP-Complete
• Palindromic Length and Reduction of Powers
• Palindromic Length of Words with Many Periodic Palindromes
• ${\mathrm{Pal}}^k$ Is Linear Recognizable Online
• Tight tradeoffs for approximating palindromes in streams
• Palindromic length sequence of the ruler sequence and of the period-doubling sequence
• Palindromic length of words and morphisms in class $\mathcal{P}$
• Palindromic Trees for a Sliding Window and Its Applications
• Palindromic length of infinite aperiodic words
• Prefix palindromic length of the Thue-Morse word
• Palindromic Decompositions with Gaps and Errors
• Block Palindromes: A New Generalization of Palindromes
• Shortest unique palindromic substring queries in optimal time
• Word Break on SLP-Compressed Texts
• Double-Ended Palindromic Trees in Linear Time