喂你脚下有坑 3年前 SPFA 最短路 算法模版 SPFA 模版 给定一个 $n$ 个点，$m$ 条边的有向图，可以使用 $O(nm)$ 的时间复杂度，求出单源点的最短路。 通常复杂度较低，在网格图等特殊情况下将被卡到复杂度的上上界。 使用方法 void SPFA::init(int n); 传入点的数量 n，初始化图 void SPFA::addEdge(int […] 算法竞赛 1.06k 0 8
喂你脚下有坑 3年前 Manacher 回文串 算法模版 Manacher 模版 在 $O(n)$ 的时间复杂度内，求出字符串 str 内部的所有回文字符串。因为回文串数量级别可能到达 $O(n^2)$，所以这里求出的是具有代表性的回文串信息，即以 str 内任意位置为中心的最长回文串。 使用方法 调用 build 函数，预处理字符串 s 的所有回文信息，函数返回 s 内最长的回 […] 其他内容 1.22k 0 7
喂你脚下有坑 4年前 KMP 字符串 模式匹配 算法模版 KMP 算法模版 给你一个模式串 T 与一个目标串 S，我们要快速找到 T 在 S 中的所有出现，复杂度为 $O(|S| + |T|)$。 需要额外说明的是这里的代码对于 Next 数组多算了一位，相当于给原本的模式串 T 后增加了一个无法匹配的字符。在匹配的过程中一旦要比较模式串无法匹配的字符，那么就说明匹配成功了 […] 算法竞赛 1.37k 0 2
喂你脚下有坑 4年前 RMQ ST表 数据结构 算法模版 ST 表模版 简介 给定一个长度为 $n$ 的数组，支持 $O(1)$ 查询区间最值。 使用前，调用 init() 函数初始化 ST，然后使用 query() 函数查询区间最值，下标范围从 $\left [0, n\right )$。 当前代码实现区间最小值问题，区间的最大值，最大公约数等均可以查询。 原理 预处 […] 算法竞赛 1.11k 4 0
