前缀函数

前置

子串

字符串中连续的一段。

前缀

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

真前缀

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

后缀

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

真后缀

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

定义

对于一个长 n 的字符串 s,我们设 i 位的前缀函数为 πi

  1. s 的子串 0i 有一对相等的真前缀真后缀,则 πi 为真前缀(真后缀)的长度。

  2. 若不止一对相等的,令 πi 为最长的长度。

  3. 若没有,则 πi=0

  4. π0=0

计算方法

朴素(暴力)

枚举:O(n3)

优化一

简单思考一下,πi+1 的值至多为 πi+1

O(n2)

优化二

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

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

所以,j(n)=πjn11

O(n)