A subquadratic algorithm for minimum palindromic factorization
We give an O(nlog?n) O ( n log ? n ) -time, O(n) O ( n ) -space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string S[1..n] S [ 1 . . n ] , in O(nlog?n) O ( n log ? n ) time our algorithm returns the minimum number of palindromes S1,,S? S 1 ,  , S ? such that S=S1?S? S = S 1 ? S ? . We also show that the time complexity is O(n) O ( n ) on average and ?(nlog?n) ? ( n log ? n ) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.
palindromes factorization string algorithms