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

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

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

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

Answer 2

创建您自己的字符串（或后缀）类，如

http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html