前缀函数

前置

子串

字符串中连续的一段。

前缀

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

真前缀

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

后缀

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

真后缀

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

定义

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