前缀函数 前缀函数的定义是：一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。 我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。 通过定义，我们可以暴力求出前缀函数 $f(i)$，复杂度 $O(n^2)$。 显然，这个复杂度太高了，于是我们可以尝试优化。 优化 第一个重…