本文章是对过去文章《KMP算法》的进一步解释与补充，使其语言叙述更加通俗简单。 KMP算法简介 算法来源 Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合…

学习差分约束算法之前，你需要先学习：最短路算法、负环 算法简介 差分约束算法是用于求解不等式组的解的一种算法。具体描述如下： 给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如： $$ \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\…

Catalan数（卡特兰数） 实际问题 有 $2n$ 个人排成一行进入剧场。入场费 $5$ 元。其中只有 $n$ 个人有一张 $5$ 元钞票，另外 $n$ 人只有 $10$ 元钞票，剧院无其它钞票，问有多少种方法使得只要有 $10$ 元的人买票，售票处就有 $5$ 元的钞票找零？ 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处…

学习扫描线，你需要先学习线段树和离散化 扫描线简介 扫描线是一种求矩形面积并/周长的好方法，同样的，它可以延伸到很多地方。注意，扫描线并不是一条存在的线，是在解释算法时的帮助我们更好理解的线。 扫描线原理 现在在平面直角坐标系中有$n$个矩形，它们相互重叠在一起，求出所有矩形占有的面积（重叠部分只算一次）。如果采用暴力枚举每一个点，那么空间与时间都…

分治法简介 主要作用 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。 分治算法是一个解决…

背包问题简介 背包问题解释 背包问题是动态规划中的经典问题，本节中会讲到多种背包问题，并对各种背包问题进行优化与转化。背包问题是指在一个有容积或者重量限制的容器中放入物品，每一个物品有不同的重量、容积、价值，要求在容器的承受范围内取得的价值最大。根据物品的限制条件不同，背包问题可以分为$01$背包、完全背包、多重背包、分组背包和混合背包问题。 背包…

倍增简介 倍增，顾名思义就是成倍总价。若问题状态的空间特别大，则一步步地推的算法复杂度太高，可以通过倍增的思想，只考察2的整数次幂的位置，快速缩小求解范围，直到找到解。 倍增原理 任意整数可以被表示成若干个$2$的次幂项之和。例如整数$5$，其二进制表示为$(101)_2$，该二进制数从右往左第$0$、$2$位均为$1$，则$5=2^2+2^0$；…

整除 定义 设$a,b \in \mathbb{Z}$，如果存在$q \in \mathbb{Z}$，使得$b=aq$，那么就可以说$b$可以被$a$整除，记作$a \mid b$，且称$b$是$a$的倍数，$a$是$b$的约数（因数、除数） 性质 $a \mid b \Longleftrightarrow -a \mid b \Longleftr…

最小生成树的介绍 生成树的定义 在一个具有$ n $个点的无向连通图中，选出$ n-1 $条边将$ n $个点连接起来，构成一棵树。 注意：只有连通图才有生成树，非连通图只有生成森林。 最小生成树的定义 我们定义无向连通图的最小生成树为边权和最小的生成树。 最小生成树算法 Kruskal算法 实现 Kruskal算法是一种常见并且好写的最小生成树算…

强联通分量简介 定义 在有向图$G$中，如果两个顶点$u,v$间有一条从$u$到$v$的有向路径，同时还有一条从$v$到$u$的有向路径，即：两个点可以互相到达，则称两个顶点强连通。如果有向图$G$的每两个顶点都强连通，称$G$是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。 强联通分量算法 Tarjan算法 主要作用 缩点求无向图…