喂你脚下有坑 3年前 Manacher 算法 回文串 字符串 Manacher 算法 问题设定 回文字符串，就是一个字符串，你从前向后读它与从后向前读它是一样的。比如：baccab 就是一个回文串，而且是一个长度为偶数的回文串（偶回文串）；bacdcab 是一个长度为奇数的回文串（奇回文串），babcb 就不是一个回文串。 这里可以发现，奇回文串的中心是一个字母，偶回文串的中心在最中 […] 算法竞赛 1.88k 0 7
喂你脚下有坑 3年前 Manacher 回文串 算法模版 Manacher 模版 在 $O(n)$ 的时间复杂度内，求出字符串 str 内部的所有回文字符串。因为回文串数量级别可能到达 $O(n^2)$，所以这里求出的是具有代表性的回文串信息，即以 str 内任意位置为中心的最长回文串。 使用方法 调用 build 函数，预处理字符串 s 的所有回文信息，函数返回 s 内最长的回 […] 其他内容 1.22k 0 7
喂你脚下有坑 4年前 区间DP 回文串 微软面试给定一个字符串，每次可以删除一个连续回文，最少几次将删完字符串。 字符串删除回文串面试题 题目大意：给定一个字符串，每次可以删除一个连续回文，最少几次将删完字符串。 思路 区间DP，$dp[l][r]$ 表示删除字符串 $l\cdots r$ 需要的最小代价。 我们可以将删除回文串的过程看作不断剥离回文串两段的相同字母，因为每一次删除回文串的代价均为 1，我们可以将删除回文串的代价记在删 […] 算法竞赛 1.15k 2 1
