Z函数 定义z[i]表示𝑠[i:]与𝑠的LCP（最长公共前缀）的长度，其中𝑠[i:]表示从𝑠[i]到𝑠[n−1]的子串（后缀串） 模板 1234567891011121314151617private int[] calcZ(int[] s, int start) { int n = s.length - start; int[] z = new int[n]; int boxL = 0; int boxR = 0; // z-box 左右边界 for (int i = 1; i < n; i++) { if (i <= boxR) { z[i] = Math.min(z[i - boxL], boxR - i + 1); } while (i + z[i] < n && s[start + z[i]] == s[start + i + z[i]]) { boxL = i; ...

dfs时间戳 深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。时间戳是DFS的一种应用，用于记录节点被访问的时间顺序。通过时间戳，我们可以了解节点的访问顺序以及子树的范围。 时间戳在许多算法中都有应用，例如： 树的重链剖分：在树的重链剖分中，时间戳用于标记节点的访问顺序。（目前主要是这个） 拓扑排序：通过DFS时间戳可以实现拓扑排序。 强连通分量：在图中找到强连通分量。 用法如下所示（记录节点的访问顺序） 123456789101112// 记录当前节点对应在字符串的区间int time = 0;private void dfs(int cur, List<Integer> g[], char cs[], char dfsStr[], int nodes[][]) { nodes[cur][0] = time; for (int nxt : g[cur]) { dfs(nxt, g, cs, dfsStr, nodes); } dfsStr[time++] = cs[cur]; nodes ...

逆元 费马小定理和逆元 在模运算中，逆元是一个非常重要的概念。如果 aaa 和 MODMODMOD 互质（即它们的最大公约数是 1），那么 aaa 在模 MODMODMOD 下的逆元 bbb 满足： ab≡1(modMOD)ab \equiv 1 \pmod{MOD} ab≡1(modMOD) 逆元实质上是乘法操作的“撤销”。在模 MODMODMOD 算术中，逆元使我们能够通过乘以逆元来“消除”一个数的影响，从而简化计算。 费马小定理告诉我们如何快速找到逆元，费马小定理是关于素数的一个定理，它提供了一种快速计算幂模的方法。如果 ppp 是一个素数，且 aaa 不是 ppp 的倍数，那么 ap−1a^{p-1}ap−1 被 ppp 除的余数总是 1。用数学语言来描述就是： ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p} ap−1≡1(modp) a∗ap−2≡1(modp)a * a^{p-2} \equiv 1 \pmod{p} a∗ap−2≡1(modp) a≡1/ap−2(modp)a \equiv 1 / a^{p-2} \pmod{p} a≡1/a ...

快速幂 在计算数的幂时，常规的做法是进行多次连乘运算，例如计算 a 的 n 次幂，就需要连乘 n 次：a a … * a。然而，当指数 n 很大时，这样的计算方式效率很低，会进行大量的重复计算。 快速幂算法（Exponentiation by Squaring）是一种优化计算幂的方法，它通过将指数 n 分解成二进制形式，并利用幂的性质进行计算，从而减少了不必要的重复计算，提高了计算效率。 模板 12345678910int MOD = (int)1e9 + 7;long pow(long x, int n) { long res = 1; while (n != 0) { if (n % 2 != 0) res = res * x % MOD; x = x * x % MOD; n /= 2; } return res;} 矩阵快速幂 12345678910111213141516171819202122232425private long[][] multi(long a[][] ...

字符串哈希 多项式字符串哈希：可以得到所有子串的哈希值 1234567891011121314151617// 多项式字符串哈希（方便计算子串哈希值）// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]char[] t = target.toCharArray();final int MOD = 1_070_777_777;final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8); // 随机 base，防止 hackint[] powBase = new int[n + 1]; // powBase[i] = base^iint[] preHash = new int[n + 1]; // 前缀哈希值 preHash[i] = hash(target[0] 到 target[i-1])powBase[0] = 1;for (int i = 0; i < n; i++) { // 计算t ...

Manacher算法 Manacher算法是一种用于查找字符串中最长回文子串的高效算法，它的时间复杂度为O(n) 算法维护一个数组P，其中P[i]表示以位置i为中心的最长回文串的半径 Manacher算法利用了回文串的对称性来加速搜索过程。如果当前考虑的位置i在之前找到的最长回文串的范围内，那么可以利用这个回文串的对称性来确定i的位置的回文半径的初始值。如果i的位置超出了之前回文串的范围，那么需要从i的位置开始进行暴力匹配来确定回文半径 在算法执行过程中，会维护一个最右端点R，它表示当前找到的最长回文串的右端点。每次找到一个新的回文串时，都会更新R的位置 Manacher 算法可以计算以s[i]（或者s[i] 和 s[i+1]）为回文中心的最长回文子串的长度。 此外，还可以： 判断任意子串是否为回文串。 计算从𝑠[𝑖] 开始的最长回文子串的长度。 计算以𝑠[𝑖] 结尾的最长回文子串的长度。 1234567891011121314151617181920212223242526272829303132class Manacher { public int[ ...

滑动窗口 对于每个问题，由于子串越长，越满足要求，有单调性，所以可以用滑动窗口解决 2962. 统计最大元素出现至少 K 次的子数组: todo 3306. 元音辅音字符串计数 II: 恰好包含k个转换为至少包含k个 - 至少包含k+1个 3413. 收集连续 K 个袋子可以获得的最多硬币数量: 不重叠区间问题，边界处理，正反两次滑窗（构造逆序相反数数组）

0-1树 概念 0-1树是字典树的一个变种，每个树节点只有0和1两个孩子，可以用来维护一些数字的异或和。 相关题解 421. 数组中两个数的最大异或值 2935. 找出强数对的最大异或值 II(2349)

博弈dp 一人最大化得分，一人最小化得分 3283. 吃掉所有兵需要的最多移动次数

值域dp 利用值域作为状态进行dp，枚举值域 3277. 查询子数组最大异或值：https://bughere.github.io/algorithm/problem/algorithm-problem-leetcode-3277/