6533b856fe1ef96bd12b1d22
RESEARCH PRODUCT
A subquadratic algorithm for minimum palindromic factorization
Gabriele FiciDominik KempaTravis GagieJuha Kärkkäinensubject
FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)PalindromeCharacterization (mathematics)Binary logarithmOmegaSubstringTheoretical Computer ScienceString algorithmComputational Theory and MathematicsFactorizationComputer Science - Data Structures and AlgorithmsC++ string handlingPalindromeDiscrete Mathematics and CombinatoricsData Structures and Algorithms (cs.DS)FactorizationTime complexityAlgorithmMathematicsComputer Science - Discrete Mathematicsdescription
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 [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm returns the minimum number of palindromes $S_1,\ldots, 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-01-01 |