引言：从字符串匹配到后缀数组
在文本处理、生物信息学和数据压缩领域，字符串匹配是最基础也最核心的操作之一。给定一个长文本 T 和模式串 P，如何快速判断 P 是否在 T 中出现？传统方法如 KMP 算法能在 O(n+m) 时间内完成单次匹配，但当需要回答大量不同模式串的查询时，预处理成本便成了瓶颈。
后缀数组（Suffix Array, SA） 正是为解决这一矛盾而生的强大数据结构。它将文本的所有后缀按字典序排序并记录起始位置，使得任意模式串的匹配问题转化为一次二分查找。配合 LCP数组（Longest Common Prefix），后缀数组还能优雅地解决最长重复子串、不同子串计数等复杂问题。
本文将用 Java 完整实现后缀数组的 倍增构造算法，讲解 SA 与 Rank 的双数组协同机制、LCP 的 Kasai 线性算法，以及多个经典应用场景。
核心概念三件套
后缀数组 SA
对于一个长度为 n 的字符串 s，其所有后缀为 s[i..n-1]（0 ≤ i < n）。后缀数组 SA 是一个长度为 n 的整数数组，其中 SA[i] 表示按字典序排列后第 i 小的后缀的起始位置。
例如，字符串 "banana" 的所有后缀为：
– 0: "banana"
– 1: "anana"
– 2: "nana"
– 3: "ana"
– 4: "na"
– 5: "a"
按字典序排序后："a"(5), "ana"(3), "anana"(1), "banana"(0), "na"(4), "nana"(2)，因此SA = [5, 3, 1, 0, 4, 2]`。
Rank 数组
Rank 数组 是 SA 的逆： Rank[i] 表示后缀 s[i..] 在排序后的名次。即 Rank[SA[i]] = i。在上例中，Rank = [3, 2, 5, 1, 4, 0]。
SA 与 Rank 的双向映射是后缀数组算法的核心——当我们需要比较两个后缀的大小时，可以通过 Rank 在 O(1) 时间内获取。
LCP 数组
LCP数组 记录排序后相邻后缀的最长公共前缀长度： LCP[i] = lcp(s[SA[i]..], s[SA[i-1]..])，通常约定 LCP[0] = 0。
对于 "banana"，LCP = [0, 1, 3, 0, 0, 2]。LCP 数组将后缀数组从”静态索引”提升为”动态分析工具”，是诸多高级应用的基础。
倍增构造算法
核心思想
直接对所有后缀进行快速排序的复杂度为 O(n log n · n) = O(n² log n)（每次比较两个后缀需要 O(n)）。倍增算法的精妙之处在于：不直接比较整个后缀，而是利用已排序的短前缀信息，在 O(1) 时间内比较长前缀。
具体而言，第 k 轮迭代中，我们已知每个位置开始的 2^(k-1) 长度前缀 的 Rank。要比较两个后缀的 2^k 长度前缀，只需比较它们的前半段和后半段的 Rank 对 (rank1, rank2)——这正是一个二元组的比较，可用基数排序在 O(n) 时间内完成。
算法框架
- 初始化：对每个字符直接排序，得到长度为 1 的 Rank。
- 倍增：令
k = 1, 2, 4, 8, ...，直到k >= n。 - 对每个位置
i，构造关键字(Rank[i], Rank[i+k])（若越界则补 -1）。 - 按关键字排序，更新 SA 和 Rank。
- 去重：相同关键字的 Rank 值必须相同。
由于每轮排序 O(n log n)，共 log n 轮，总复杂度为 O(n log² n)。若使用基数排序（计数排序实现），可优化至 O(n log n)。
Kasai 线性 LCP 算法
朴素计算 LCP 需要 O(n²)，而 Kasai 算法 能在 O(n) 时间内完成。
关键观察：设 h = LCP[Rank[i]]，则 LCP[Rank[i+1]] ≥ h - 1。这是因为去掉首字符后，后缀 s[i+1..] 与 s[SA[Rank[i]-1]+1..] 的公共前缀至少为 h-1，而 LCP 的定义是相邻排序后缀的公共前缀，实际值只会更大。
算法流程：
1. 利用 Rank 数组定位每个后缀在 SA 中的位置。
2. 按原字符串顺序遍历，维护当前高度 h。
3. 若当前后缀不是 SA 中第一个，则与 SA 中前一个后缀逐字符比较，更新 h。
4. 每次比较后 h 最多增加 n，而总共最多减少 n，故总复杂度 O(n)。
Java 完整实现
import java.util.Arrays;
/**
* 后缀数组完整实现
* 包含：倍增构造、Kasai LCP算法、最长重复子串、不同子串计数
* 时间复杂度：O(n log n) 构造，O(n) 计算LCP
*/
public class SuffixArray {
private final String text;
private final int n;
private final int[] sa; // 后缀数组
private final int[] rank; // Rank数组
private final int[] lcp; // LCP数组
/**
* 构造后缀数组
* @param text 原始字符串（假设不含特殊分隔符，内部处理时会补0）
*/
public SuffixArray(String text) {
this.text = text;
this.n = text.length();
this.sa = new int[n];
this.rank = new int[n];
this.lcp = new int[n];
build();
buildLCP();
}
/**
* 倍增算法构造后缀数组
* 使用Java内置排序比较关键字对，复杂度 O(n log² n)
* 实际应用中可替换为基数排序优化至 O(n log n)
*/
private void build() {
// 初始轮：按单个字符排序
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = i;
rank[i] = text.charAt(i); // 用ASCII码作为初始rank
}
// 倍增：k 为当前比较的前缀长度
for (int k = 1; k < n; k <<= 1) {
final int kk = k;
final int[] rankRef = rank;
// 按 (rank[i], rank[i+k]) 排序
Arrays.sort(order, (a, b) -> {
if (rankRef[a] != rankRef[b]) {
return Integer.compare(rankRef[a], rankRef[b]);
}
// 越界处理：后半段不存在时视为 -1（最小）
int ra = (a + kk < n) ? rankRef[a + kk] : -1;
int rb = (b + kk < n) ? rankRef[b + kk] : -1;
return Integer.compare(ra, rb);
});
// 临时rank，相同关键字共享同一rank
int[] tmpRank = new int[n];
tmpRank[order[0]] = 0;
for (int i = 1; i < n; i++) {
int prev = order[i - 1];
int curr = order[i];
boolean same = rankRef[prev] == rankRef[curr];
if (same) {
int r1 = (prev + kk < n) ? rankRef[prev + kk] : -1;
int r2 = (curr + kk < n) ? rankRef[curr + kk] : -1;
same = r1 == r2;
}
tmpRank[curr] = tmpRank[prev] + (same ? 0 : 1);
}
System.arraycopy(tmpRank, 0, rank, 0, n);
// 提前终止：所有rank互不相同，已完全排序
if (rank[order[n - 1]] == n - 1) {
break;
}
}
for (int i = 0; i < n; i++) {
sa[i] = order[i];
}
}
/**
* Kasai 线性算法计算 LCP 数组
* 关键性质：LCP[Rank[i+1]] >= LCP[Rank[i]] - 1
*/
private void buildLCP() {
// 构建 rank 的逆：rank[i] 表示 suffix i 在 SA 中的位置
// 此时 rank 已经是最终版本
int[] invSA = new int[n];
for (int i = 0; i < n; i++) {
invSA[sa[i]] = i;
}
int h = 0;
for (int i = 0; i < n; i++) {
int pos = invSA[i];
if (pos == 0) {
lcp[pos] = 0; // 第一个元素无左邻居
continue;
}
int j = sa[pos - 1]; // SA中前一个后缀的起始位置
// 从当前h开始比较，逐步扩展
while (i + h < n && j + h < n && text.charAt(i + h) == text.charAt(j + h)) {
h++;
}
lcp[pos] = h;
if (h > 0) h--; // 下一个位置的LCP至少为h-1
}
}
// ==================== 查询接口 ====================
public int[] getSA() { return sa; }
public int[] getRank() { return rank; }
public int[] getLCP() { return lcp; }
/**
* 获取第 i 小的后缀字符串（调试用）
*/
public String getSuffix(int i) {
return text.substring(sa[i]);
}
// ==================== 经典应用 ====================
/**
* 应用1：最长重复子串
* 原理：任意两个后缀的LCP即为它们的公共前缀，LCP数组的最大值即为最长重复子串长度
* @return [长度, 起始位置1, 起始位置2]
*/
public int[] longestRepeatedSubstring() {
int maxLen = 0;
int pos = -1;
for (int i = 1; i < n; i++) {
if (lcp[i] > maxLen) {
maxLen = lcp[i];
pos = i;
}
}
if (maxLen == 0) return new int[]{0, -1, -1};
return new int[]{maxLen, sa[pos], sa[pos - 1]};
}
/**
* 应用2：不同子串计数
* 原理：以 SA[i] 开始的所有后缀贡献 n - SA[i] 个子串，但其中与前一个后缀重复的
* 子串数量为 LCP[i]。因此新增子串数为 n - SA[i] - LCP[i]。
* @return 不同子串的总数
*/
public long countDistinctSubstrings() {
long count = 0;
for (int i = 0; i < n; i++) {
count += (n - sa[i]) - lcp[i];
}
return count;
}
/**
* 应用3：模式串匹配（二分查找）
* 利用 SA 的有序性，在 O(m log n) 时间内判断模式串是否出现
* @param pattern 待匹配模式串
* @return 是否存在
*/
public boolean contains(String pattern) {
int m = pattern.length();
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
String suffix = text.substring(sa[mid], Math.min(sa[mid] + m, n));
int cmp = suffix.compareTo(pattern);
if (cmp < 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
if (lo < n) {
String candidate = text.substring(sa[lo], Math.min(sa[lo] + m, n));
return candidate.equals(pattern);
}
return false;
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
System.out.println("===== 示例1：基础构造与查询 =====");
String s1 = "banana";
SuffixArray sa1 = new SuffixArray(s1);
System.out.println("文本: " + s1);
System.out.println("SA: " + Arrays.toString(sa1.getSA()));
System.out.println("Rank: " + Arrays.toString(sa1.getRank()));
System.out.println("LCP: " + Arrays.toString(sa1.getLCP()));
System.out.println("后缀列表:");
for (int i = 0; i < s1.length(); i++) {
System.out.printf(" SA[%d]=%d -> \"%s\" (LCP=%d)%n",
i, sa1.getSA()[i], sa1.getSuffix(i), sa1.getLCP()[i]);
}
System.out.println("\n===== 示例2：最长重复子串 =====");
String s2 = "abcdabcfabcg";
SuffixArray sa2 = new SuffixArray(s2);
int[] lrs = sa2.longestRepeatedSubstring();
System.out.println("文本: " + s2);
System.out.printf("最长重复子串长度: %d, 位置: %d 和 %d%n",
lrs[0], lrs[1], lrs[2]);
if (lrs[0] > 0) {
System.out.println("子串内容: \"" + s2.substring(lrs[1], lrs[1] + lrs[0]) + "\"");
}
System.out.println("\n===== 示例3：不同子串计数 =====");
String[] testStrings = {"banana", "aaaa", "abcde", "abcdabcfabcg"};
for (String ts : testStrings) {
SuffixArray saTmp = new SuffixArray(ts);
long distinct = saTmp.countDistinctSubstrings();
long expected = (long) ts.length() * (ts.length() + 1) / 2;
System.out.printf("\"%s\": 不同子串=%d, 总子串=%d%n", ts, distinct, expected);
}
System.out.println("\n===== 示例4：模式串匹配 =====");
String s4 = "mississippi";
SuffixArray sa4 = new SuffixArray(s4);
String[] patterns = {"issi", "sip", "abc", "ppi"};
for (String p : patterns) {
boolean found = sa4.contains(p);
System.out.printf("contains(\"%s\") = %b%n", p, found);
}
System.out.println("\n===== 示例5：大规模性能测试 =====");
StringBuilder sb = new StringBuilder();
java.util.Random rand = new java.util.Random(42);
int scale = 50000;
for (int i = 0; i < scale; i++) {
sb.append((char) ('a' + rand.nextInt(26)));
}
String large = sb.toString();
long start = System.nanoTime();
SuffixArray saLarge = new SuffixArray(large);
long elapsed = System.nanoTime() - start;
System.out.printf("规模: n=%d, 构造耗时: %.3f ms%n", scale, elapsed / 1_000_000.0);
System.out.printf("LCP最大值: %d%n", Arrays.stream(saLarge.getLCP()).max().getAsInt());
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 后缀数组构造 | O(n log² n) | O(n) | Java 内置排序实现；基数排序可优化至 O(n log n) |
| LCP 数组（Kasai） | O(n) | O(n) | 线性扫描，利用高度单调性 |
| 模式串匹配 | O(m log n) | O(1) | m 为模式串长度，基于 SA 二分查找 |
| 最长重复子串 | O(n) | O(1) | 遍历 LCP 取最大值 |
| 不同子串计数 | O(n) | O(1) | 利用 SA 与 LCP 的线性公式 |
扩展与变体
后缀自动机（Suffix Automaton）
后缀自动机是后缀数组的”压缩版”，用 O(n) 状态表示所有子串信息，支持在线构造。它在子串出现次数查询、最短未出现子串等问题上表现更优，但实现复杂度也更高。
后缀树（Suffix Tree）
后缀树是所有后缀的 Trie 压缩形式，与后缀数组 + LCP 在信息上等价（通过笛卡尔树可互转）。后缀树的构造（Ukkonen 算法）为 O(n)，但常数较大且实现复杂。实际工程中，后缀数组往往是更平衡的选择。
最长公共子串（LCS）
给定两个字符串 A 和 B，将它们用不会出现的分隔符连接为 A#B$，构建后缀数组。属于 A 和 B 的后缀之间的最大 LCP 即为最长公共子串长度。通过遍历 LCP 并判断相邻后缀来源即可在 O(|A|+|B|) 内解决。
总结
后缀数组是字符串算法的基石之一。通过本文你掌握了：
- 后缀数组、Rank 数组与 LCP 数组的定义与关系
- 倍增构造算法的核心思想：利用短前缀 Rank 在 O(1) 内比较长前缀
- Kasai 线性算法的巧妙之处：高度单调递减约束
- 完整可运行的 Java 实现，涵盖构造、LCP 计算与三大经典应用
- 时间/空间复杂度分析与算法选型建议
从生物序列比对到代码相似度检测，从搜索引擎索引到数据压缩，后缀数组的思想渗透在现代计算的诸多角落。掌握这一数据结构，将为你打开字符串算法的大门。
