前缀函数

一个 border 是同时出现在字符串两端的同一段内容。已知 $s[0..i-1]$ 的最长 border 长度为 $j$ 时，加入新字符 $s[i]$，最乐观的候选只是把原 border 延长一位：比较 $s[i]$ 与 $s[j]$。候选不可能一次增长两位，因为删掉新字符后就会得到一个比 $j$ 更长的旧 border，与 $j=\pi [i-1]$ 矛盾。

如果这两个字符失配，并不需要把候选降到零。任何仍可能延长的候选，必须既是 $s[0..j-1]$ 的真 border，又是当前前缀的后缀；其中最长者正是 $\pi [j-1]$。于是反复执行

会按长度从大到小枚举全部可行 border，而不会漏掉中间候选。这个“最长 border 的最长 border”链，就是前缀函数压缩重复结构的方式。

算法结束一轮时维持如下不变量：$j$ 是能与 $s[i]$ 相容的最长旧 border，若字符相等则延长为 $j+1$，否则在 $j=0$ 时得到零。正确性来自候选链的完备性；线性复杂度则来自候选长度的单调记账。外层每前进一步，$j$ 最多增加 $1$；while 中每次回退都会严格减小 $j$，总下降量不可能超过此前的总上升量。再计入每个位置常数次比较，时间为 $O(n)$，空间为存储数组所需的 $O(n)$。

字符串 aabaaab 的前缀函数为

前五个字符 aabaa 的最长 border 是 aa，所以 $\pi [4]=2$。处理位置 $5$ 的字符 a 时，长度 $2$ 的候选期待下一个字符为 b，发生失配；回退到 $\pi [1]=1$ 后，长度 $1$ 的 border 可以用 a 延长，于是 $\pi [5]=2$。这里新值仍为 $2$，但它来自较短 border 的重新延长，而不是保留了已经失配的候选。处理最后的 b 时，aa 可延长为 aab，得到 $\pi [6]=3$。

前缀函数保存的是长度，不是字符下标。候选长度为 $j$ 时，下一个待比较字符是 $s[j]$；回退目标是 $\pi [j-1]$。把它误写成 $\pi [j]$，既混淆长度与下标，也可能无法严格缩短候选而陷入循环。0 同时表示空 border 和没有更短候选，不代表首字符已经匹配。

若要列出整个字符串长度 $n$ 的所有非空 border，先取 $k=\pi [n-1]$，再依次取 $k=\pi [k-1]$，直到零。每个 border 长度 $k$ 都给出一个周期候选 $n-k$；但只有当 $n$ 能被 $n-k$ 整除时，字符串才是该长度块的整数次幂。把“存在周期”与“恰由一个块重复组成”混为一谈，会产生错误的周期判断。

词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。与序列公理库序列Sequence以自然数为定义域的函数。给出离散对象，前缀函数则为每个前缀组织 border 链。KMP公理库KMP 算法Knuth–Morris–Pratt algorithm利用模式自身前后缀信息避免文本指针回退的线性时间字符串匹配算法。把这条链用作模式失配后的状态回退；本条只负责解释 $\pi$ 的定义、构造和结构性质，文本扫描与匹配报告由 KMP 条目承担。

前缀出现次数也能由同一棵失败链汇总。先把每个位置贡献给其 $\pi [i]$，再按长度从大到小把计数累加给 $\pi [k-1]$，就会把较长前缀的每次出现传给它的所有 border；最后还要为每个非空前缀计入它作为自身出现的那一次。若将模式 $P$、一个不在字母表中的分隔符 # 和文本 $T$ 拼成 P#T，则拼接串上值等于 $|P|$ 的位置恰对应完整匹配；分隔符不可省略，否则 border 可能跨越模式与文本的边界。

前缀函数与Z 函数公理库Z 函数Z-function · Z-array记录从每个位置开始的后缀与整个字符串前缀的最长公共前缀长度。都编码字符串前缀与其他位置的重合信息，并可在线性时间互相转换；equivalent_to 指的是信息层面的可恢复性，不表示两个数组逐项相等，也不表示两套更新公式可以混用。若预处理对象从单个模式改成固定全文，则应转向 FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。 等全文索引；那是查询模型的改变，而不是前缀函数的另一种写法。