前缀函数
前缀函数
前置
子串
字符串中连续的一段。
前缀
指从字符串开头到某个位置结束的特殊子串
真前缀
指从字符串开头到某个位置结束的特殊子串(不包含字符串本身)
后缀
指从某个位置开始到字符串结尾的特殊子串
真后缀
指从某个位置开始到字符串结尾的特殊子串(不包含字符串本身)
定义
对于一个长
若
的子串 有一对相等的真前缀与真后缀,则 为真前缀(真后缀)的长度。若不止一对相等的,令
为最长的长度。若没有,则
计算方法
朴素(暴力)
枚举:
优化一
简单思考一下,
优化二
在寻找真前缀与真后缀时,我们会枚举一个长度
当匹配失败时,我们希望找到仅次于
所以,