形式陈述

字符串 $T$ 长度为 $n$，后缀数组 $SA[0..n-1]$ 是起始位置的排列，使后缀 $T[SA[i]..]$ 按字典序非降排列。逆数组记录每个后缀的秩；$LCP[i]$ 通常是相邻后缀 $SA[i-1]$ 与 $SA[i]$ 的最长公共前缀长度。倍增构造按长度 $2^k$ 前缀秩对排序，可达 $O(n\log n)$ 或相应排序界；存在更复杂的线性构造。模式可在后缀数组上二分查找。

直觉

任意子串都是某个后缀的前缀。后缀按字典序排列后，拥有共同前缀的后缀聚成连续区间，于是子串问题转为有序数组和区间问题。

例子与边界

对附加唯一终止符的 banana，对应的 ana 型后缀与 anana 型后缀相邻且 LCP 为 3。终止符小于其他字符且只出现一次，可统一前缀比较约定，但并非所有实现必需。朴素二分每次比较模式可能花 $O(m)$，查询为 $O(m\log n)$；结合 LCP 可改进。后缀数组只给排序，不自动包含所有 LCP 或快速区间最值结构。字符编码顺序必须与期望字典序一致。

推论与应用

后缀数组用于全文索引、重复子串、最长公共子串、压缩和生物序列分析，相比后缀树更紧凑且缓存友好。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997，Chs. 1–8。