罗罗编程学习记录
本页内容 展开查看

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
  • [ ] 费用流与上下界网络流