KMP 匹配算法

​ RE：从零开始的字符串学习

暴力做法

​ 首先将两个字符串首位对齐，逐位匹配，完成匹配后将模式串位置后移一位。

​ 时间复杂度为：$O(nm)$，其中 $n,m$ 分别表示主串和模式串的长度。

鸽巢原理及应用

​ 就简单的概述一下了

简单形式

​ 现有 $n+1$ 个物品，要将他们放入 $n$ 个盒子里，那么必定有 $1$ 个盒子内至少有 $2$ 个物品。

​ 显然，我们考虑每个盒子里都只能放置 $1$ 个物品，那么会有 $1$ 个物品剩余，所以易证。

求导基础及常用函数的导数

​ 一些微积分的基础知识。

关于求导

​ 我们对于一个函数所求的导函数实为：基于其图像中的每一点求其斜率的函数表达式。

​ $f`(x)$ 表示函数 $f(x)$ 的导函数，那么就有：

$\lim_{h\rightarrow0}\frac{f(x+h)-f(x)}{h}$

整数分块

​ 现在来补一下小知识

例子

$\sum_{i=1}^{n}\frac{n}{i}$

​ 求上式。

牛顿二项式定理

$(x+y)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} {x}^{k} {y}^{\alpha-k} \tag{0 $\leq$ |x| < |y| }$

容斥：错位排列

​ 令 {$1,2,...,n$} 的一个错位排列，是一个排列 ${a_1,a_2,...,a_n}$，使得 ${a_1}\ne{1},{a_2}\ne{2},...,{a_n}\ne{n}$。

​ 令 $D_n$ 表示大小为 $n$ 的错位排列的方案数。

容斥：有限元素多重集合

这里主要是补一下之前的留的坑。

常用组合数公式的证明

​ 证明中可能用到的一些前置知识，这里我不再给出他们证明：

$(x+y)^n=\sum_{k=0}^n{\binom{n}{k}{x}^{k}{y}^{n-k}}\tag{1}$

$\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}\tag{2}$

​ 上述是著名的二项式公式和帕斯卡公式，下面我们将利用他们对另外的一些组合数公式予以证明。

偏序集和等价关系

​ 不得不说关于离散数学的定义太抽象，而实在难以理解。

$Ramsey$ 定理

​ 这一节是关于鸽巢原理的部分拓展，其实用处并不太大吧