如何在7+中线性空间构建一个后缀数组？

Question

在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是字符串的长度。

在Java7和更高版本中，有什么快速简单的方法可以做到这一点吗？

Answer 1

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

• size()
• get(int n) -返回第n个element
• equals(int n, String s) -将第n个元素与input
• ...

进行比较

• 根据需要提供访问器方法，例如：
• size()
• get(int n)-返回第n个元素与input
• ...

比较第n个元素

• 存储它收到的字符串，其他任何内容

• 根据需要提供访问器方法

​

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

Answer 2

创建您自己的字符串(或后缀)类，如下所示

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