LCP 数组

LCP 数组不保存任意两后缀的最长公共前缀，而只保存后缀数组中相邻后缀之间的值。相邻性却足以恢复任意区间：字典序中两个后缀的公共前缀，会被夹在它们之间的相邻后缀边界中的最小公共前缀卡住，因此答案等于两者排名之间所有相邻 LCP 的最小值。这个“全局查询化为区间最小”是它最重要的结构意义。

字符串 banana 的相邻排序后缀展示重复串结构。LCP 数组只记录相邻后缀；直接把非相邻答案当成某一个数组项会出错，必须取区间最小值。

字符串 banana 的后缀按序大致为 a,ana,anana,banana,na,nana，相邻 LCP 为 $1,3,0,0,2$。后缀 ana 与 anana 的 LCP 为 $3$；a 与 anana 的 LCP 则是对应区间最小值 $min(1,3)=1$。

LCP 值按字符数计，不是后缀数组下标差。重复字符很多时朴素逐对比较会退化为二次时间，Kasai 算法利用相邻起点的 LCP 至少下降一这一事实线性构造。

后缀数组公理库后缀数组Suffix array按字典序排列字符串全部后缀起始位置的数组索引。 提供字典序，数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。 保存相邻值，词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。 提供后缀对象。对 LCP 数组建 RMQ 可回答任意两后缀的 LCP；最长重复子串、后缀比较与分组、不同子串计数、字符串聚类和后缀树的紧凑替代或模拟都依赖这一组合。

Suffix array 中任意两后缀的 LCP 等于它们秩区间内相邻 LCP 的最小值，因此可用RMQ公理库静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。回答；后缀树公理库后缀树Suffix tree对加入唯一终止符后的全部后缀构造路径压缩 Trie，并以原文本区间表示边标签。则把同一公共前缀表示为 LCA 的字符串深度。FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。主要用 BWT 区间做模式搜索，LCP 可辅助压缩后缀树拓扑或定位，但不是 backward search 的必要定义。三条接口应按数组 RMQ、显式树和压缩索引区分。