算法模板

1 字符串

• 字符串匹配：kmp、mancher、z函数、滚动哈希
• 最小表示法
• 字典树
• AC自动机
• 后缀数组

2 常用数据结构

• 常用数据结构：位运算、链表、栈、并查集、st表、树状数组、线段树

3 图论

• 树上问题：lca、点分治
• 环问题：拓扑排序、基环树
• 最短路：dijkstra、floyd、Bellman-Ford、spfa
• 连通性：割点、桥、强连通分量、双连通分量
• 图匹配：二分图最大匹配、二分图最大权完美匹配
• 网络流：最大流、最小费用最大流

4 数学

• 数论：质因数分解、乘法逆元
• 线性代数：矩阵快速幂
• 排列组合：下一个排列
• 随机化：爬山法
• 计算几何：

5 dp

• 数位 dp
• 插头 dp
• dp 优化：wqs 二分、斜率优化、四边形不等式优化