1. 演算法學習筆記(83): Manacher演算法
Manacher演算法，俗稱馬拉車，是一種專門處理迴文子串問題的演算法。迴文串有奇偶兩種形式：奇迴文串和偶迴文串。奇迴文串相較於偶迴文串更易處理，因其存在唯一的中心點。通過在原字元串兩端添加一個不在字元集內的特殊字元，如空格或特定符號，可以將奇迴文串轉變成以普通字元為中心的奇迴文串，而偶迴文串則會變為以特殊字元為中心的奇迴文串。
對於字元串S，定義一個數組P，表示以字元為中心的奇迴文串的數量。在預處理後，P中的值對應原字元串中以特殊字元為中心的迴文串。最長的迴文子串長度是P中的最大值。
Manacher演算法通過遍歷字元串並維護中心點與邊界點的位置，高效求解P數組。與Z演算法類似，演算法流程中，數組P值遞增，內層循環執行次數不超過字元串長度，因此演算法復雜度為線性。
2. 迴文序列問題
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。
時間復雜度： O(n^2) 兩個for循環
空間復雜度： O(n^2) dp數組的大小
給你一個字元串 s，請你將 s 分割成一些子串，使每個子串都是 迴文串 。返回 s 所有可能的分割方案。
迴文串 是正著讀和反著讀都一樣的字元串。
示例 1：
輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]
思路：動態規劃得到每個子串是否為迴文子串，然後從頭開始回溯演算法
時間復雜度：O(N * 2^N)
給你一個字元串 s，請你將 s 分割成一些子串，使每個子串都是迴文。
返回符合要求的 最少分割次數 。
示例 1：
輸入：s = "aab"
輸出：1
解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個迴文子串。
思路：
時間復雜度=空間復雜度=O(n^2)
給你一個字元串 s ，請你統計並返回這個字元串中 迴文子串 的數目。
迴文字元串 是正著讀和倒過來讀一樣的字元串。
子字元串 是字元串中的由連續字元組成的一個序列。
具有不同開始位置或結束位置的子串，即使是由相同的字元組成，也會被視作不同的子串。
示例 1：
輸入：s = "abc"
輸出：3
解釋：三個迴文子串: "a", "b", "c"
給你一個字元串 s ，找出其中最長的迴文子序列，並返回該序列的長度。
子序列定義為：不改變剩餘字元順序的情況下，刪除某些字元或者不刪除任何字元形成的一個序列。
示例 1：
輸入：s = "bbbab"
輸出：4
解釋：一個可能的最長迴文子序列為 "bbbb" 。
給定一個字元串 S，找出 S 中不同的非空迴文子序列個數，並返回該數字與 10^9 + 7 的模。
通過從 S 中刪除 0 個或多個字元來獲得子序列。
如果一個字元序列與它反轉後的字元序列一致，那麼它是迴文字元序列。
如果對於某個 i，A_i != B_i，那麼 A_1, A_2, ... 和 B_1, B_2, ... 這兩個字元序列是不同的。
示例 1：
輸入：
S = 'bccb'
輸出：6
解釋：
6 個不同的非空迴文子字元序列分別為：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 雖然出現兩次但僅計數一次。