Given a string *S* with length *n*, design a linear time algorithm to decompose *S* into several palindromic substrings that their concatenation is *S*.

**Solution**:

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), 2*F*(*S*, 1) – 1, or 2*F*(*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)、2*F*(*S*, 1) – 1或是2*F*(*S*, 1) + 1，*F*(*S*, *i*)為最小的索引*j*使得S[*i*..*j*]是一回文。利用動態規劃的技巧就可在線性時間內建構出分解。

Reference: Geeksforgeeks

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