前缀函数

前置

子串

字符串中连续的一段。

前缀

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

真前缀

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

后缀

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

真后缀

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

定义

对于一个长 \(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)\)