先记住这个答案
前缀函数 π[i] 定义为 s[0..i] 的最长真前缀同时是其后缀的长度。求法是从左到右计算，假设已知 π[i-1]=j，比较 s[i] 与 s[j]；若相等则 π[i]=j+1，否则令 j=π[j-1] 并继续比较，直到 j=0。每次比较后要么加一，要么 j 严格递减，总回退次数不超过 O(n)，因此线性时间。
- 最多增加 1 次
- 总回退 O(n)
- 失配沿 pi 跳
线性构造核心机制
设 s 下标从 0 开始，π[0]=0。计算 π[i] 时，先设 j=π[i-1]，这表示 s[0..i-1] 的长度为 j 的后缀等于前缀。若 s[i]==s[j]，则该匹配可以向右扩展一位，因此 π[i]=j+1。这个观察保证了前缀函数单步最多增加 1，不会出现从 2 跳到 4 的情况。
当 s[i]≠s[j] 时，不能直接扩展，需要在 s[0..j-1] 中找更短的、且仍是 s[0..i-1] 的后缀的串。这正是 π[j-1]：它是 s[0..j-1] 的最长真前后缀，因而也一定与以 i-1 结尾的长度为 π[j-1] 的后缀相等。于是令 j=π[j-1] 重复比较，直到 j=0。由于 j 每次减少至少 1，而总增加不超过 n，回退总次数为 O(n)。
function computePrefix(s) {
const n = s.length;
const pi = new Array(n).fill(0);
let j = 0;
for (let i = 1; i < n; i++) {
while (j > 0 && s[i] !== s[j]) {
j = pi[j - 1];
}
if (s[i] === s[j]) {
j++;
}
pi[i] = j;
}
return pi;
}
console.log(JSON.stringify(computePrefix('abcabcd')));
console.log(JSON.stringify(computePrefix('aabaaab')));
console.log(JSON.stringify(computePrefix('aaaa')));
console.log(JSON.stringify(computePrefix('a')));
console.log(JSON.stringify(computePrefix('')));查看输出与解释
[0,0,0,1,2,3,0]
[0,1,0,1,2,2,3]
[0,1,2,3]
[0]
[]该实现直接对应线性递推：外层循环 n-1 次，内层 while 总执行次数 O(n)。空串长度为 0，返回空数组。
处理长文本连续重复模式
假设要在由 100 万个字母 a 组成的文本中查找模式串 "aaaa" 的每次出现。朴素方法在每个位置都匹配 4 个字符，总比较约 400 万，但前缀函数法先计算模式串自身的内链，进入匹配时失配极少。在连续 a 的情况下，π 值一直增长到模式长度，文本指针不回退，线性完成。
关键在于模式串的前缀函数能提前发现其周期性。当模式内部有大量重叠时，文本匹配阶段每读一个字符，若等于预期字符就直接 j 加一；即使失配，也可以回退到较短的相等前后缀，而不是从头开始。这个决策让比较次数维持在文本长度加上模式长度量级，而不是乘上重复次数。
易错边界与失效条件
最容易忽略的情况是模式串长度 1。此时 π[0]=0，没有后续递推，单独写分支或用循环 i=1 自然处理，但若在失配回退时访问 pi[j-1]，需保证 j>0，否则越界。此外空串没有前缀函数，调用前应判断。对全相同字符的串，π[i]=i，若误以为 π[i] 受某个上限限制且未正确更新，可能得出错误循环节。
再看例如 "ababa"，π 序列为 [0,0,1,2,3]，计算 π[4] 时 j 从 π[3]=2 起，s[4]='a' 与 s[2]='a' 相等，直接得 3，无需回退。真正需要连续回退的示例是 "abacabab"，其末尾可能先跳到一个较短相等前后缀再继续比较。内层 while 总执行次数仍是 O(n)，与字符集大小无关；若回退总次数超过 n，则说明实现有误。
容易答错的地方
- 认为前缀函数可以增加超过 1
- 有人猜 π[i] 可以突然从 2 变到 5，但不可能。若 π[i]=2，则长度大于 3 的公共前后缀去掉最后一个字符就会构成长度至少 3 的公共前后缀，矛盾。因此单步至多加 1，这是线性时间的基础。
- 回退时恢复 j=0
- 失配时直接置 j=0 会让复杂度上升为 O(n^2)，并丢失已匹配信息。应该用 j=π[j-1]，因为新候选后缀必须同时是 s[0..j-1] 的后缀，这样才能与已比较部分一致。
面试官还会怎么问？
前缀函数能否用滚动哈希优化？
滚动哈希只能快速比较两段是否相等，不能直接判断是否为最长；若配合二分查找，复杂度为 O(n log n)，不如现有线性递推。前缀函数本无需随机性，所以一般不用哈希优化。
如何用前缀函数求每个前缀的出现次数？
可以。先求出 π 数组，令 cnt 为长度 n+1 的数组并全部初始化为 1（表示长为 1..n 的前缀至少出现一次），然后 for i from n down to 2: cnt[π[i-1]] += cnt[i]，最终 cnt[i] 就是长为 i 的前缀出现次数，整体 O(n)。
π 数组与 Z 数组信息等价吗？
可互相转换，但各自递推顺序不同。KMP 用已算的 π 做回退，Z 则维护 [l,r] 区间避免重复比较，实现风格不同。
参考资料
示例用于理解所注明的运行环境与边界；延伸学习可结合原文中的更多案例。