Given a string S with length n, design a linear time algorithm to decompose S into several palindromic substrings that their concatenation is S.
Let F(S, i) be the smallest index j, such that S[i..j] is an even palindrome. This function can be computed in a way similar to Manacher algorithm. Then, we can greedily decompose S into several even palindromic substrings.
In general, greedy decomposition may not work. However, we can prove that if S can be decompose, then the length of the first palindromic substring is one of F(S, 1), 2F(S, 1) – 1, or 2F(S, 1) + 1, where F(S, i) is the smallest index j that S[i..j] is a palindrome. Consequently, we can solved this problem in linear time by dynamic programming.
It is also possible to test whether a string is a composition of two, three, or four palindromes in linear time.
令F(S, i)為最小的索引j使得S[i..j]是一個偶回文。此函數可藉由Manacher algorithm計算。借此可以利用貪心法把S分解成數個偶回文。
一般而言，貪心分解可能不存在。但是我們可以證明如果S存在一組分解，那第一個切點只會是F(S, 1)、2F(S, 1) – 1或是2F(S, 1) + 1，F(S, i)為最小的索引j使得S[i..j]是一回文。利用動態規劃的技巧就可在線性時間內建構出分解。
Zvi Galil and Joel Seiferas, “A Linear-Time On-Line Recognition Algorithm for “Palstar,” Journal of the ACM (JACM) JACM Homepage archive Volume 25 Issue 1, Jan. 1978 Pages 102-111