KMP
KMP 算法是用于求在一个字符串中是否存在一个子串与另一个字符串相同的算法。
引入
例 1：给定两个字符串 $s_1,s_2$，求 $s_1$ 在 $s_2$ 中的所有出现位置。
naive：
考虑暴力匹配，枚举起点，不断判断 $s_{1,i+j-1}=s_{2,j}$ 即可。
时间复杂度：$O(nm)$。
KMP：
注意到，暴力匹配较慢的原因是每次匹配失败后，都要从 $j=1$ 重新开始。但是实际上，完全可以利用上一次匹配的结果，简化匹配次数。
假设起点为 $i$ 时，匹配到 $j$，那么下一次从 $i+1$ 开始匹配，若能匹配的比 $i$ 作为起点更远，则从 $i+1$ 开始一段连续字符一定是 $s_2$ 的一段前缀，同时也是 $s_1[i,i+j-1]$ 的一段后缀，也就是说 $s_1[i+1,i+j-1]$ 是 $s_2[1,j]$ 的最大 Border。而如果 $i+1$ 不能比 $i$ 匹配的更远，那么肯定不应该考虑。
综上，得到一个结论：从 $i$ 开始下一个可能会匹配成功的位置，一定是 $s_2$ 的 Border，
具体而言，匹配失败后，可以直接在 $i+(j-Border_j+1)$ 开始接着匹配。（其中，$Border_j$ 指的是 $s_2[1,j]$ 的 Border）
时间复杂度：$O(|s_1|+|s_2|)$。
同求 Border，将匹配时的起止点视作两个指针，两个指针都是单调递增的，所以时间复杂度是线性的。