A Subquadratic Algorithm for Minimum Palindromic Factorization

Gabriele Fici, Travis Gagie, Juha Kärkkäinen +1

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…