# 1745. Palindrome Partitioning IV (回文树)

```struct Tree
{
int next[4005][30];
int fail[4005];
int cnt[4005];
int num[4005];
int len[4005];
int s[4005];
int p;
int n;
int last;

int new_node(int x)
{
memset(next[p], 0, sizeof(next[p]));
len[p] = x;
num[p] = 0;
cnt[p] = 0;

return p++;
}

void init()
{
p = 0;
new_node(0);
new_node(-1);
n = 0;
last = 0;
fail[0] = 1;
s[0] = -1;
}

int get_fail(int x)
{
while (s[n - len[x] - 1] != s[n])
x = fail[x];
return x;
}

{
x -= 'a';
s[++n] = x;
int cur = get_fail(last);
if (!(last = next[cur][x]))
{
int now = new_node(len[cur] + 2);
fail[now] = next[get_fail(fail[cur])][x];
next[cur][x] = now;
num[now] = num[fail[now]] + 1;
cnt[now]++;
last = now;
return 1;
}

cnt[last]++;
return 0;
}
void count()
{
for (int i = p - 1; i >= 0; i--)
{
cnt[fail[i]] += cnt[i];
}
}
};

class Solution {
public:
vector<vector<int>> num;
bool fun(int x, int y)
{
if(x < 0 && y < 3)
{
return false;
}
if (y == 3)
{
if (x == -1)
return true;
return false;
}

for (int i = 0; i < num[x].size(); i++)
{
if(fun(num[x][i] - 1, y + 1))
return true;
}
return false;
}
bool checkPartitioning(string s) {
Tree tree = Tree();
tree.init();

for (int i = 0; i < s.length(); i++)
{
vector<int> m;
int x = tree.last;
m.push_back(i - tree.len[x] + 1);
while (tree.fail[x] > 0)
{
x = tree.fail[x];
m.push_back(i - tree.len[x] + 1);
}

num.push_back(m);
}

return fun(s.length() - 1, 0);
}
};```

0 条评论

• ### LeetCode 1745. 回文串分割 IV（区间DP）

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

• ### palindrome - 132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a pa...

• ### Leetcode 132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a p...

• ### [Leetcode][python]Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II

将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。

• ### Leetcode 131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a p...

• ### palindrome - 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a pa...

• ### ​LeetCode刷题实战132：分割回文串 II

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 回溯/贪心高频题

"有关递归的算法，都离不开“树”的遍历这一抽象模型。只不过对于不同的算法，在前（中）后序遍历的时候，所做的事不同而已。 "

• ### ​LeetCode刷题实战131：分割回文串

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，题目就从LeetCode上面选 ！

• ### LeetCode 131 Palindrome Partitioning

思路是，先将所有的回文子串都找出来，记录下左右端点。 然后DFS这些子串就可以了。

• ### LeetCode 214. Shortest Palindrome(回文串，回文树，KMP)

https://leetcode.com/problems/shortest-palindrome/

• ### ​LeetCode刷题实战131：分割回文串

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 狗家算法面试高频题汇总

Google 面试题 | Data Stream Median - Python版

• ### CodeForces 17E Palisection(回文树)

E. Palisection time limit per test 2 seconds memory limit per test 128 meg...

• ### 三十分钟成为 Contributor | 提升 TiDB Parser 对 MySQL 8.0 语法的兼容性

TiDB 的一大特性就是和 MySQL 高度兼容，目标是让用户能够无需修改代码即可从 MySQL 迁移至 TiDB。要达成这个目标，需要完成两个提升兼容性的任务...

• ### HDU 5157 Harry and magic string(回文树)

Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...