Java后缀数组之求sa数组的实例代码

Java后缀数组是一种经典的字符串匹配算法，可以实现快速求解字符串的后缀数组（sa数组）。下面我们将介绍如何在Java中编写求解sa数组的实例代码。

步骤一：构造后缀数组

首先我们需要准备一个包含原始字符串所有后缀的数组（称为“后缀数组”）。这个数组的元素类型为Suffix，其中Suffix类的定义如下：

class Suffix implements Comparable<Suffix> {
    int index;  // 后缀的起始下标
    String suffix;  // 后缀的内容

    public Suffix(int index, String suffix) {
        this.index = index;
        this.suffix = suffix;
    }

    @Override
    public int compareTo(Suffix o) {
        return this.suffix.compareTo(o.suffix);
    }
}

我们可以在该类的构造函数中为每个后缀指定起始下标，并按照字典序排序。

构造后缀数组的代码示例：

public static void constructSuffixArray(String str, Suffix[] suffixes) {
    for (int idx = 0; idx < str.length(); ++idx) {
        suffixes[idx] = new Suffix(idx, str.substring(idx));
    }
    Arrays.sort(suffixes);
}

步骤二：求解sa数组

已经构造好后缀数组后，我们可以通过Suffix.index获取每个后缀的起始下标，即sa数组的值。

代码示例1：使用for循环遍历suffixes数组，并按顺序记录每个后缀的起始下标，即可得到sa数组。

public static int[] getSuffixArray(Suffix[] suffixes) {
    int[] sa = new int[suffixes.length];
    for (int idx = 0; idx < suffixes.length; ++idx) {
        sa[idx] = suffixes[idx].index;
    }
    return sa;
}

代码示例2：使用java.util.stream库中的mapToInt()方法将suffixes数组映射成int类型的sa数组，更加简洁。

public static int[] getSuffixArray(Suffix[] suffixes) {
    return Arrays.stream(suffixes).mapToInt(Suffix::getIndex).toArray();
}

以上是Java后缀数组之求sa数组的完整攻略。