看了 tly 的 blog 挺有感触的，于是决定把难学难懂（至少对于我这种较钝的人来说）的字符串算法进行梳理与总结（也有新知，有了新的认识会重写）。

这是个长期计划，希望不会咕。

§ Part. 0 用语

∆ Part. 0-1 符号

定义字符串 $A,B$（从 $1$ 开始编号，以 C++ 的 char* 来理解吧）。

• $|A|$：字符串 $A$ 的长度。
• $A\sqsubset B$： $A$ 为 $B$ 前缀。
• $A\sqsupset B$： $A$ 为 $B$ 后缀。
• $A=B_{|A|}$：同 $A\sqsubset B$。
• $A=B_{-|A|}$：同 $A\sqsupset B$。
• $A[l,r]$：$A$ 的 $[l,r]$ 子串。
• $A_{1}\cdots A_{n}$：将 $n$ 个字符串 $A_{i}$ 拼接起来。
• $A^{k}$：把 $k$ 个 $A$ 拼接起来。

∆ Part. 0-2 用语

• Border：

§ Part. 1 KMP

∆ Part. 1-1 KMP 的内容

说一下所谓 next 数组的本质：所有前缀的最大 border。