前缀函数的学习报告

江湖午餐票 · 2025-03-28 12:51:34 · 算法·理论

在字符串算法的世界中，前缀函数犹如一把精巧的钥匙，能够高效解开模式匹配、子串搜索、字符串最小周期等经典难题。无论是代码优化还是算法竞赛，理解前缀函数的思想，都能让我们在字符串处理中游刃有余。

本文是笔者对于网络上大量文章的总结和提炼，如有不严谨之处欢迎指正。参考资料的链接已经放在文末，侵权自删。

1. 前缀函数

1.1 前缀函数的定义[^i]

对于一个长度为 n 的字符串 s，其前缀函数被定义为一个长度为 n 的数组 \pi。其中 \pi[i] 为子串 s[0\dots i] 最长的、相等的真前缀与真后缀的长度，即最大公共前后缀长度（最长 Border 的长度）。

用数学语言描述如下：

特别地，规定 \pi[0]=0。

1.2 前缀函数的求解

假设已知 \pi[0\dots i-1]，考虑 \pi[i] 的转移。

易得若 s[0\dots i-1] 中存在第 j 长度的 Border k^{(j)} ，使得 s[k^{(j)}]=s[i]，则 \pi[i] 一定可以从 k^{(j)}+1 转移而来。

则问题就变成了根据前缀函数求字符串的所有 Border 问题，详见2.1 字符串的 Border，这里直接给出结论：

则伪代码如下：

k = pi[i-1]

while k>0 && s[i]!=s[k]:
    k = pi[k-1]
# 不断回溯前一个可能的最长 Border
if s[k] == s[i]:
    pi[i] = k+1

2. 应用

2.1 字符串的所有 Border

本部分其实是 Border 自身的递归性质，如果仅仅是看文字证明的话是非常难理解的，各位可以画个图、多推几个样例感受一下。

对于一个长度为 n 字符串 s，若已得最长的 Border 长度 k^{(1)}=\pi[n-1]，考虑 k^{(2)} 的转移。

根据 Border 的定义

同理

由以上二者关系可得

因为 k^{(2)} 是长度上仅次于 k^{(1)} 的最长的 Border，那么 k^{(2)} 也一定是子串 s[0\dots k^{(1)}-1] 最长 Border。

所以可得 k^{(2)}=\pi[k^{(1)}-1]，数学归纳后便可得到

2.2 字符串的匹配算法