深入理解后缀数组（Java语言实现详解：从零构建高效字符串处理算法）

为什么使用后缀数组？

相比后缀树，后缀数组更节省内存，且易于实现。它是解决以下问题的利器：

• 查找最长重复子串
• 查找两个字符串的最长公共子串
• 快速字符串匹配
• 数据压缩（如BWT变换）

掌握Java后缀数组的构建方法，是提升你字符串处理算法能力的关键一步。

Java实现后缀数组（O(n log²n) 方法）

最直观的方法是生成所有后缀，然后排序。但这样时间复杂度高（O(n² log n)）。我们可以使用“倍增法”优化到 O(n log²n)。下面是一个清晰易懂的 Java 实现：

import java.util.*;public class SuffixArray {    public static int[] buildSuffixArray(String s) {        int n = s.length();        // suffixes[i] 表示从 i 开始的后缀        Integer[] suffixes = new Integer[n];        for (int i = 0; i < n; i++) {            suffixes[i] = i;        }        // 使用自定义比较器排序        Arrays.sort(suffixes, (a, b) -> s.substring(a).compareTo(s.substring(b)));        // 转换为 int[]        return Arrays.stream(suffixes).mapToInt(Integer::intValue).toArray();    }    public static void main(String[] args) {        String text = "banana";        int[] sa = buildSuffixArray(text);        System.out.println("后缀数组: " + Arrays.toString(sa));        // 输出: [5, 3, 1, 0, 4, 2]    }}

上面的代码虽然简洁，但由于每次比较都调用 substring()，实际效率不高。在真实项目中，我们通常采用更高效的后缀数组排序算法，比如基于倍增和基数排序的方法。

优化版：倍增法（推荐）

以下是更高效的 O(n log n) 实现思路（简化版，适合学习）：

public class OptimizedSuffixArray {    public static int[] buildSuffixArray(String s) {        int n = s.length();        int[] sa = new int[n];        int[] rank = new int[n];        int[] newRank = new int[n];        // 初始化：按单个字符排序        for (int i = 0; i < n; i++) {            sa[i] = i;            rank[i] = s.charAt(i);        }        for (int k = 1; k < n; k *= 2) {            final int[] r = rank.clone();            Arrays.sort(sa, (i, j) -> {                if (r[i] != r[j]) return r[i] - r[j];                int ri = (i + k < n) ? r[i + k] : -1;                int rj = (j + k < n) ? r[j + k] : -1;                return ri - rj;            });            // 重新计算 rank            newRank[sa[0]] = 0;            for (int i = 1; i < n; i++) {                newRank[sa[i]] = newRank[sa[i - 1]] +                     ((r[sa[i]] == r[sa[i - 1]] &&                       (sa[i] + k < n ? r[sa[i] + k] : -1) ==                       (sa[i - 1] + k < n ? r[sa[i - 1] + k] : -1)) ? 0 : 1);            }            System.arraycopy(newRank, 0, rank, 0, n);        }        return sa;    }    public static void main(String[] args) {        String text = "banana";        int[] sa = buildSuffixArray(text);        System.out.println(Arrays.toString(sa)); // [5, 3, 1, 0, 4, 2]    }}

这个版本避免了创建子字符串，通过比较当前长度为 k 的前缀的“排名”来排序，效率更高。

总结

通过本教程，你已经学会了：

• 什么是后缀数组及其应用场景
• 如何用 Java 构建基础版后缀数组
• 如何优化实现以提升性能

掌握后缀数组实现不仅能帮助你应对算法面试，还能在实际开发中高效处理大规模文本数据。建议你动手敲一遍代码，加深理解！

关键词回顾：Java后缀数组、后缀数组实现、字符串处理算法、后缀数组排序。