形式陈述

对字符串 $s$，定义

$$\pi [i]=max\{k<i+1:s[0..k-1]=s[i-k+1..i]\}.$$

计算 $\pi [i]$ 时，若当前候选边界失配，就沿 $\pi [j-1]$ 退到次长边界，直到匹配或归零。由于候选长度总增量为 $O(n)$、回退也被其抵消，整体时间 $O(n)$。

直觉

一个前缀的所有可能边界形成由“最长边界的最长边界”递归得到的失配链。

例子与边界

字符串 ababa 的最后一个前缀函数值为 3，对应边界 aba。前缀函数记录的是长度，不是模式在文本中的出现次数；空串边界约定应统一。

推论与应用

它是 KMP 的真正状态摘要，并用于周期、border 树和字符串自动机。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), prefix function and KMP.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), prefix function.