LCP 数组

字典序中，拥有同一前缀的字符串形成连续区间。若首尾两条后缀都以长度 $h$ 的串开头，夹在中间的后缀也必须以它开头，故每个相邻 $LCP$ 都至少为 $h$。反过来，若每对相邻后缀的前 $h$ 个字符相同，沿区间传递就得到首尾也有这段共同前缀。两向论证给出上述区间最小值等式。

banana 的相邻值 ​

后缀数组为 $SA=(5,3,1,0,4,2)$，对应

于是 $LCP=(0,1,3,0,0,2)$。ana 与 anana 相邻，共同前缀长 $3$；a 与 anana 的秩为 $0,2$，共同前缀长为 $min(LCP[1],LCP[2])=min(1,3)=1$。加上终止符的 banana$ 会多出最小后缀 $，数组和下标也要相应改变。

Kasai 构造：长度每步至多下降一 ​

按文本起点顺序，定义 $h_p=LCP[ISA[p]]$。核心性质是

即从一个起点移到下一个，已有公共前缀长度至多下降一，也可能增加很多；不是每步至少下降一。

若 $h_p\ge 2$，令 $q$ 为后缀 $T[p..n)$ 的字典序前驱。删掉两串相同的首字符后，$T[q+1..n)$ 仍小于 $T[p+1..n)$，且二者共有至少 $h_p-1$ 个前缀字符。$T[p+1..n)$ 的真正相邻前驱夹在它们之间，由前缀区间性质同样至少共享这 $h_p-1$ 个字符。$h_p\le 1$ 时，下界由非负性直接成立。若下一后缀已是字典序最小者，该论证也说明此前不可能有 $h_p\ge 2$。

据此可从已知的下界继续比较，而不从零开始。假定 $SA$ 正确、字符访问和比较为常数成本：

def lcp_array(text, sa):
    n = len(text)
    isa = [0] * n
    for rank, start in enumerate(sa):
        isa[start] = rank
    lcp = [0] * n
    h = 0
    for p in range(n):
        rank = isa[p]
        if rank == 0:
            h = 0
            continue
        q = sa[rank - 1]
        while p + h < n and q + h < n and text[p + h] == text[q + h]:
            h += 1
        lcp[rank] = h
        h = max(h - 1, 0)
    return lcp

每个正常迭代结束时 $h$ 至多减一，最小后缀的那次迭代进入时已有 $h=0$；因此成功比较的总增量为 $O(n)$。每个起点再花常数次边界或失配检查，总时间为 $O(n+1)$。$ISA$ 与输出数组各占 $O(n)$ 个整数单元；这不包含构造 $SA$ 的成本。

最大 $LCP$ 值给出最长重复非空子串的长度，默认允许两次出现重叠。统计不同非空子串时，第 $r$ 条后缀有 $n-SA[r]$ 个前缀，其中恰有 $LCP[r]$ 个已由更小后缀覆盖，因此

这里不能把 $LCP$ 的相邻秩下标与 Kasai 扫描的文本起点混用；下降性质描述的是 $LCP[ISA[p]]$，不是 $LCP[r+1]$ 相对 $LCP[r]$。

后缀树理路后缀树Suffix tree对加入唯一终止符后的全部后缀构造路径压缩 Trie，并以原文本区间表示边标签。把两条后缀的公共前缀表示为叶子 LCA 的字符串深度；LCP 加 RMQ 则用数组给出同一查询结果。FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。的基本反向搜索使用 BWT 与 rank，LCP 可辅助其他导航，却不是该计数接口自动附带的组成部分。