前缀函数

前置

子串

字符串中连续的一段。

前缀

指从字符串开头到某个位置结束的特殊子串

真前缀

指从字符串开头到某个位置结束的特殊子串（不包含字符串本身）

后缀

指从某个位置开始到字符串结尾的特殊子串

真后缀

指从某个位置开始到字符串结尾的特殊子串（不包含字符串本身）

定义

对于一个长 $n$ 的字符串 $s$，我们设 $i$ 位的前缀函数为 ${\pi }_i$

1. 若 $s$ 的子串 $0\sim i$ 有一对相等的真前缀与真后缀，则 ${\pi }_i$ 为真前缀（真后缀）的长度。

2. 若不止一对相等的，令 ${\pi }_i$ 为最长的长度。

3. 若没有，则 ${\pi }_i=0$

4. ${\pi }_0=0$

计算方法

朴素（暴力）

枚举：$O(n^3)$

优化一

简单思考一下，${\pi }_{i+1}$ 的值至多为 ${\pi }_i+1$

$O(n^2)$

优化二

在寻找真前缀与真后缀时，我们会枚举一个长度 $j$

当匹配失败时，我们希望找到仅次于 $j$ 的长度 $j^{(2)}$，其中 $j^{(2)}$ 我们希望他满足前缀性质。

所以，$j^{(n)}={\pi }_{j^{n-1}-1}$

$O(n)$