前缀函数 & KMP 学习笔记 2024-7-06 21:28 | 103| 0| 未分类| 2024-7-06 21:36 | ztrztr 510 字| 3 分钟 前缀函数 前缀函数的定义是:一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。 我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。 通过定义,我们可以暴力求出前缀函数 $f(i)$,复杂度 $O(n^2)$。 显然,这个复杂度太高了,于是我们可以尝试优化。 优化 第一个重… 字符串