前缀函数

一个 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”链，就是前缀函数压缩重复结构的方式。

每轮的 while 沿候选链排除无法延长的 border，直到找到最长可延长候选，或退回长度零。随后的字符比较把候选延长一位；若长度零仍失配，就令 $\pi [i]=0$。候选链的完备性保证这就是最长的新 border。

线性复杂度来自候选长度的记账：外层每前进一步，$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，在 $n\ge 1$ 时先取 $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 [i]$，再按长度从大到小把计数累加给 $\pi [k-1]$，就会把较长前缀的每次出现传给它的所有 border；最后还要为每个非空前缀计入它作为自身出现的那一次。若将非空模式 $P$、一个不在字母表中的分隔符 # 和文本 $T$ 拼成 P#T，则拼接串上值等于 $|P|$ 的位置恰对应完整匹配；分隔符不可省略，否则 border 可能跨越模式与文本的边界。

前缀函数与Z 函数理路Z 函数Z-function · Z-array记录每个后缀与整个字符串前缀的最长公共前缀长度，并通过最右匹配区间在线性时间计算的数组。都编码字符串前缀与其他位置的重合信息，可在线性时间互相恢复；它们记录的长度含义不同，各有相应的构造算法。若要对固定全文回答许多模式查询，FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。 等全文索引则把预处理工作放在文本一侧。