内容参考： 牛客竞赛字符串专题-calabash_boy 樱雪喵-广义后缀自动机（广义 SAM）学习笔记 KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ，即一个字符串同长度的完全相同的前后缀（通常不含自身）。 KMP 的做法是先求出要匹配的字符串（短串）的所有前缀的最长 Border，然后在于长串进行匹配，并在无法匹配…

博客参考：CSDN 的 文章, enceladus, yybyyb, hyfhaha 的代码启示，皎月半洒花 的 博客, hyfhaha 的 博客。 前置知识 I - KMP字符串匹配 模版：Luogu3375。 我觉得这玩意儿比 trie 树难理解一点。 给定两个字符串 $s_1$ 和 $s_2$，我们需要求出 $s_2$ 在 $s_1$ 中所有…