形式陈述

若后缀数组 $SA$ 按字典序排列所有后缀，则常定义

$$LCP[i]=\mathrm{lcp}(s[SA[i-1]..],s[SA[i]..])(i>0).$$

任意两个后缀在后缀数组区间中的 LCP，等于相应 LCP 数组区间的最小值，因此可与 RMQ 结合回答后缀 LCP 查询。 Kasai 算法利用相邻起点的 LCP 至少下降一这一事实在线性时间构建。

直觉

字典序中两个后缀之间的公共前缀，被夹在它们之间的相邻后缀边界中的最小公共前缀卡住。

例子与边界

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

推论与应用

用于最长重复子串、后缀比较、字符串分组、不同子串计数和后缀树的紧凑替代表示。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), suffix array and LCP.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), suffix array and LCP.