LeetCode 1745. 回文串分割 IV（分为三个回文串，manacher）

本文主要是介绍LeetCode 1745. 回文串分割 IV（分为三个回文串，manacher），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个字符串 s ，如果可以将它分割成三个非空回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为回文字符串。

示例 1：

输入：s = “abcbdd”
输出：true
解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。
示例 2：

输入：s = “bcbddxy”
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

3 <= s.length <= 2000
s 只包含小写英文字母。

思路：
最简单的是n^2 DP思路，维护 $d p [i] [j]$ 代表 $[i, j]$ 部分字符串是否回文，不再赘述。
通过马拉车算法可以做到O(n)，依据的是下面这个结论，证明没有很看懂…（何逊大佬的题解）

在这里插入图片描述
由此，可以枚举回文前缀，再枚举后面部分的最长回文前缀和最长回文后缀，看是否存在合法情况。

class Solution {
public:void manacher(vector<int>& f, vector<int>& R, string& s) {int id = 0, mx = 0;int n = s.size();for(int i = 0;i < n;i++) {if(i < id + mx) {f[i] = min(id + mx - i, f[id * 2 - i]);}while(i - f[i] - 1 >= 0 && i + f[i] + 1 < n && s[i - f[i] - 1] == s[i + f[i] + 1]) f[i]++;if(id + mx < i + f[i]) {id = i;mx = f[i];}R[i - f[i]] = f[i];}for(int i = 1;i < n;i++) {R[i] = max(R[i - 1] - 1, R[i]);}}bool checkPartitioning(string s) {string str = "#";for(int i = 0;i < s.size();i++) {str += s[i];str += "#";}int n = str.size();vector<int>dp(n, 0);vector<int>R(n, 0);manacher(dp, R, str);vector<bool>pre(n, 0);int lst = 1;for(int i = 1;i < n;i++) {if(dp[i] == i) {//维护后半部分的最长回文后缀while(lst < n && (dp[lst] != n - 1 - lst || lst - dp[lst] - 1 <= i + dp[i])) {lst++;}if(lst >= n - 1) break;int l = i + dp[i] + 1, r = lst - dp[lst] - 1, pos = (l + r) >> 1;if(dp[pos] >= r - pos) {return true;}//维护后半部分的最长回文前缀int L = l + R[l] * 2 + 1, R = n - 1;pos = (L + R) >> 1;if(L < R && dp[pos] >= R - pos) {return true;}}}return false;}
};