java - 如何在线性空间中用 Java 7+ 构建后缀数组？

Question

在 Pre-java 7 中，我可以简单地执行以下操作:

public static String[] suffixes(String s)
{
    int N = s.length();
    String[] suffixes = new String[N];
    for (int i = 0; i < N; i++)
    suffixes[i] = s.substring(i, N);
    return suffixes;
}

但是，在 Java 7 中，substring 方法返回一个新的字符串。因此消耗的空间将为 O(n^2)，其中 n 是字符串的长度。

有什么快速简便的方法可以在 Java 7 及更高版本中执行相同的操作？

Answer 1

你当然可以发明一个抽象数据类型来表示“后缀数组”:

• 用字符串初始化
• 只存储它收到的字符串
• 根据需要提供访问器方法，例如:
  • 大小()
  • get(int n) - 返回第 n 个元素
  • equals(int n, String s) - 将第 n 个元素与输入进行比较
  • ...

根据您期望从该结构中获得的功能，以不同的格式存储底层字符串可能是有意义的，例如 char[]，或者两者兼而有之。这并不重要，这将是一个实现细节，封装的，对您的 ADT 用户隐藏的。首先创建一个 interface 并定义它需要支持的方法。