前言：作者想学 $\text{AC}$ 自动机，所以，就学了一下这个算法。
$\text{Part 1. KMP}$ 字符串匹配 (暴力）$O(|s_1||s_2|)$
所谓 $\text{KMP}$ 字符串匹配，是在文本串 $s_1$ 里快速查找 $s_2$ 的一种算法。
设 $|s_1|$ 表示文本串 $s_1$ 的长度，$|s_2|$ 表示模式串 $s_2$ 的长度。
- 暴力：$O(|s_1||s_2|)$
有三个指针 $L_1,R_1$ 和 $R_2$，分别指向 $s_1$ 的左端点和右端点，$s_2$ 的左端点，。
每次比较 $s_1[R_1]$ 和 $s_2[R_2]$，看是否匹配：
- 匹配 显然当前满足条件，$R_1$ 和 $R_2$ 同时向右移
- 失配 不满足条件，说明以当前不满足条件，$L_1$ 向右移一位，然后将 $R_1$ 还原为 $L_1$，$R_2$ 还原为 $0$。
为了让 $R_2$ 赋为一个合适的值，引入了 $\text{PMT}$ 部分匹配表。
$\text{Part 2.PMT}$ 部分匹配表 ($\text{KMP}$ 字符串匹配 (优化) )
设 $\text{PMT}_i=k$，则有 $s_0+s_1+...+s_{k-1}=s_{i-k+1}+s_{i-k+2}+...+s_i$，且 $k$ 为最大值。
设 $s=\text{'abaabba'}$，给一张表：
$\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s: \text{a | b | a | a | b | b | a}$
$\text{PMT}\text{}: \text{ 0 | 0 | 1 | 1 | 2 | 1 | 2}$
若失配，则 $R_2=\text{PMT}_{R_2-1}$，即将 $R_2$ 移动到前缀匹配最大值的后一个位置，以此来减少 $R_2$ 的移动次数。
$\text{Part 3.PMT}$ 部分匹配表求值 (暴力) $O(|s_2|^2)$
$O(|s_2|^2)$，即 $O(|s_2|)$ 的时间遍历 $s_2$，在每次遍历中都用 $O(|s_2|)$ 的时间来求出 $\text{PMT}_i$。
$\text{Part 4.PMT}$ 部分匹配表求值 (优化) （自己匹配自己）
令 $R_1=1,R_2=0$，开始 $\text{PMT}$。
为 $\text{AC}$ 自动机埋下伏笔。