什么是莫队算法？

莫队算法（Mo's Algorithm）是一个由前国家队队长莫涛发明的，用于处理一系列 区间查询 问题的离线算法。它非常巧妙，本质上是一种“优雅的暴力”。

莫队算法适用于那些“从 [L, R] 的答案可以轻松（通常是 O(1)）地推导出 [L, R+1], [L, R-1], [L+1, R], [L-1, R] 的答案”的题目。例如，查询区间内不同元素的个数。

核心思想

什么是拓扑排序？

拓扑排序是对 有向无环图 (Directed Acyclic Graph, DAG) 的顶点进行的一种线性排序。该排序满足这样的条件：对于图中任意一条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 的前面。

简单来说，拓扑排序就是一种能把图“拉直”成一条线性的序列，并保证所有的依赖关系（边的方向）都得到满足的排序方式。一个有向图能进行拓扑排序的 充要条件 是它是一个 DAG。

什么是最小生成树 (MST)？

在一个 无向连通图 中，一个 生成树 是图的一个子图，它包含了图中所有的顶点，并且是一棵树（即，没有环）。一个图可以有多个生成树。

最小生成树 (Minimum Spanning Tree, MST) 是指在一个带权的无向连通图中，所有生成树里，边的权重之和最小的那一棵。

Kruskal 算法的核心思想

Kruskal 算法是一种基于 贪心策略 的最小生成树算法。它的思想非常直观和简单：

什么是 Floyd-Warshall 算法？

Floyd-Warshall 算法（简称 Floyd 算法）是一种用于计算 所有顶点对之间最短路径 的算法。与 Dijkstra 和 SPFA 不同，它不是单源最短路算法，而是一次性计算出图中任意两点之间的最短距离。

Floyd 算法可以正确处理带有 负权边 的图，但不能处理带有 负环 的图。它非常适合用于稠密图。

核心思想：动态规划

Floyd 算法的本质是一个动态规划。我们定义一个二维数组 dp[k][i][j]，表示从顶点 i 到顶点 j，只允许经过编号从 1 到 k 的顶点作为中间点时，所能得到的最短路径长度。

什么是 SPFA 算法？

SPFA（Shortest Path Faster Algorithm）是一种用于计算单源最短路径的算法。与 Dijkstra 算法不同，SPFA 可以处理带有 负权边 的图。它实际上是 Bellman-Ford 算法的一种队列优化版本。

核心思想

SPFA 算法的核心思想是 动态逼近。它维护一个队列，队列中存放着“刚刚被成功松弛过”的顶点。只有当一个顶点的距离 dist[u] 变小时，它才有可能去更新它的邻居 v 的距离 dist[v]。因此，只有那些距离值变小的顶点，才需要被放入队列中，作为下一轮松弛操作的出发点。

什么是二分图最大匹配？

• 二分图: 一个图的顶点可以被分为两个独立的集合 U 和 V，使得所有的边都连接 U 和 V 中的顶点，而 U 或 V 内部没有边。
• 匹配: 图中的一个边的集合，其中任意两条边都没有公共的顶点。
• 最大匹配: 一个图中，包含边数最多的匹配。

什么是后缀自动机 (SAM)？

后缀自动机（Suffix Automaton, SAM）是一个强大而精巧的数据结构，它能接受一个字符串 S 的所有后缀。更神奇的是，它实际上也接受了 S 的 所有子串。SAM 是一个既包含字符串所有子串信息，又具有最小节点和边数的有向无环图（DAG）。

对于一个长度为 n 的字符串，SAM 的空间复杂度和在线构建的时间复杂度都是线性的 O(n)。

核心概念

1. 状态 (State): SAM 中的每个节点代表一个状态，每个状态对应着原字符串中一个或多个子串的集合。
2. 转移 (Transition): 状态之间的有向边代表字符的转移。从状态 u 到 v 有一条字符 c 的转移边，表示在 u 所代表的子串集合中的所有字符串末尾添加字符 c 后，得到的新字符串都属于 v 所代表的子串集合。
3. 后缀链接 (Suffix Link): 这是 SAM 最核心的概念之一。每��非初始状态都有一个后缀链接，指向另一个状态。状态 u 的后缀链接指向状态 v，表示 v 所代表的子串集合是 u 所代表的子串集合中 所有字符串 的 最长后缀，且这些后缀也存在于 v 的子串集合中。所有后缀链接最终都会指向初始状态，形成一棵树状结构（Parent Tree）。

什么是 Manacher 算法？

Manacher 算法是一种用于在 线性时间内 找到字符串中最长回文子串的算法。传统的中心扩展法时间复杂度为 O(n²)，而 Manacher 算法通过利用回文串的对称性，避免了大量重复的比较，达到了 O(n) 的效率。

核心思想

Manacher 算法的核心在于维护一个 回文半径数组 p 和两个变量：

• p[i]: 以字符 i 为中心的回文串的半径长度。
• max_right: 当前已发现的所有回文串中，右边界能到达的最远位置。
• center: 对应 max_right 的那个回文串的中心位置。

什么是 AC 自动机？

AC 自动机（Aho-Corasick Automaton）是一种高效的、基于字典树（Trie）和 KMP 思想的字符串匹配算法。它能够在一个主文本串中，同时查找多个模式串的存在，且时间复杂度为线性 O(N+M)，其中 N 是主文本串长度，M 是所有模式串的总长度。

核心思想

AC 自动机巧妙地结合了两种数据结构的优点：

1. Trie (字典树): 用来存储所有的模式串。Trie 的结构使得所有模式串共享公共前缀，节省了空间。
2. 失败指针 (Fail Pointer): 这是 AC 自动机的精髓，类似于 KMP 算法中的 next 数组。每个 Trie 节点都有一个失败指针。节点 u 的失败指针指向的节点 v，代表了从根到 v 的路径所形成的字符串，是“从根到 u 的路径所形成的字符串”的 最长真后缀，并且这个后缀本身也是一个模式串的前缀。

什么是 KMP 算法？

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主文本串 S 中查找一个模式串 P 的出现位置。它的核心优势在于，当匹配过程中发生不一致时，它能利用已经匹配过的信息，跳过一些不必要的比较，从而避免了暴力匹配中的指针回溯，将时间复杂度优化到线性 O(n+m)。

核心思想：next 数组

KMP 算法的精髓在于一个预处理过的 next 数组（有时也叫 lps 数组，表示最长公共前后缀 Longest Proper Prefix which is also Suffix）。next[i] 存储的是模式串 P 的子串 P[0...i] 中，最长的相等的前缀和后缀的长度。