02.12 图与字符串进阶
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 强连通分量与 Tarjan、割点桥
- 网络流与二分图匹配
- LCA 与树上算法
- 字符串进阶(AC 自动机、后缀数组、Manacher)
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.12.1 | 强连通分量与 Tarjan 及割点桥 | Tarjan SCC、Kosaraju、割点桥、缩点 DAG |
| 02.12.2 | 网络流与二分图匹配 | Ford-Fulkerson、Dinic、匈牙利、KM、最小割最大流 |
| 02.12.3 | LCA 与树上算法 | 倍增 LCA、Tarjan 离线、树链剖分、树上差分、重心直径 |
| 02.12.4 | 字符串进阶 | AC 自动机、后缀数组、Manacher、字符串哈希 |
面试题索引
| 编号 | 题目 | 难度 | 状态 | 备注 |
|---|---|---|---|---|
| 02.12.1-001 | Tarjan 求强连通分量 | 高级 | 已完成 | |
| 02.12.1-002 | Kosaraju 算法 | 进阶 | 已完成 | |
| 02.12.1-003 | 割点判定 | 进阶 | 已完成 | |
| 02.12.1-004 | 桥判定 | 进阶 | 已完成 | |
| 02.12.1-005 | 缩点 DAG | 高级 | 已完成 | |
| 02.12.1-006 | Tarjan 伪代码 | 高级 | 已完成 | |
| 02.12.1-007 | 强连通分量应用 | 进阶 | 已完成 | |
| 02.12.1-008 | 点双与边双连通分量 | 高级 | 已完成 | |
| 02.12.2-001 | 最大流 Ford-Fulkerson | 高级 | 已完成 | |
| 02.12.2-002 | Dinic 算法 | 高级 | 已完成 | |
| 02.12.2-003 | 匈牙利算法二分图最大匹配 | 进阶 | 已完成 | |
| 02.12.2-004 | KM 算法带权二分图 | 高级 | 已完成 | |
| 02.12.2-005 | 匈牙利 vs KM 区别 | 基础 | 已完成 | |
| 02.12.2-006 | 最小割最大流定理 | 进阶 | 已完成 | |
| 02.12.2-007 | 二分图最小顶点覆盖 | 进阶 | 已完成 | |
| 02.12.2-008 | 网络流应用场景 | 基础 | 已完成 | |
| 02.12.3-001 | LCA 暴力法 | 基础 | 已完成 | |
| 02.12.3-002 | LCA 倍增法 | 进阶 | 已完成 | |
| 02.12.3-003 | LCA Tarjan 离线 | 高级 | 已完成 | |
| 02.12.3-004 | 树链剖分重链 | 高级 | 已完成 | |
| 02.12.3-005 | 树上差分 | 进阶 | 已完成 | |
| 02.12.3-006 | 树的重心与直径 | 基础 | 已完成 | |
| 02.12.3-007 | 倍增预处理 | 进阶 | 已完成 | |
| 02.12.3-008 | 树链剖分应用 | 高级 | 已完成 | |
| 02.12.4-001 | AC 自动机多模式匹配 | 高级 | 已完成 | |
| 02.12.4-002 | AC 自动机构建 fail 指针 | 高级 | 已完成 | |
| 02.12.4-003 | 后缀数组 SA 原理 | 高级 | 已完成 | |
| 02.12.4-004 | Manacher 最长回文 | 进阶 | 已完成 | |
| 02.12.4-005 | KMP 回顾与边界 | 基础 | 已完成 | |
| 02.12.4-006 | 字符串哈希 | 基础 | 已完成 | |
| 02.12.4-007 | AC 自动机 vs Trie | 基础 | 已完成 | |
| 02.12.4-008 | 各算法复杂度对比 | 基础 | 已完成 |
待整理清单
- [ ] 后缀自动机 SAM
- [ ] 动态树 Link-Cut Tree
- [ ] 费用流与上下界网络流