暑假集训知识点整理
写在前面：
本文总结自信息学奥赛一本通《算法高效进阶》
\(kmp\):
1.如果前缀\(i\)存在一个长为\(j\)的公共前后缀，那么它有一个长为\(i-j\)的周期P4391
2.用一个\(t\)串,令其长度为\(n\)，去匹配\(s\)串,令其长度为\(m\)，\(kmp[i]\)即表示\(s[1\sim i]\)与\(t[1 \sim kmp[i]]\)匹配,我们枚举\(t\)串不同的起始位，就可以将\(t\)的任意子串与\(s\)串匹配,\(O=(nm)\)P5546
并查集：
1.带权并查集P1196
2.扩展域并查集:用于同一个块维护多个信息，块与块之间有多重关系P2024
3.连通块常与并查集有关系P2700
4.并查集的连通块可以表示两个数是否已经有一定的关系了
5.并查集灵活起来感觉真的挺抽象的
最小生成树：
1.\(prim\):\(O=(n^2)\),稠密图使用
2.\(kruskal\):\(O=(mlogm+m)\)，稀疏图使用
3.广义的最小生成树就是贪心，边权可以灵活设置 最短时间