如何高效地形成后缀数组？

Question

我正在寻找一种在Java中创建后缀数组的方法。
我找到了两种可能的变体。而且我想更加深入地了解这些变体之间的不同之处。
包括运行时间和空间。

代码（后缀）：

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;
}

代码（StringBuilder后缀）：

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

问题：

• 如何高效地生成后缀数组？

- user2271868

---

使用StringBuilder版本不会改善substring的性能。无论哪种方式，它们的功能几乎相同。（事实上，在旧版本的Java中使用StringBuilder可能稍微慢一些，不包括创建StringBuilder对象本身的开销。） - Hot Licks

第一个片段具有“线性时间和线性空间”。第二个片段具有“二次时间和二次空间”。 - catch23

Answer 1

你描述的两种方法没有明显的区别：因为Java中的String是不可变的，每个后缀都会创建一个新对象。与分配和复制所需的设置新字符串对象相比，从String或StringBuilder中创建子字符串在性能上并没有太大差异。

当你寻找后缀时，传递结束索引并非必要：使用重载的单个int参数的方法即可。

for (int i = 0; i < N; i++)
    suffixes[i] = s.substring(i);

- Sergey Kalinichenko

---

在早期版本的Java中，String.substring有时会实现为共享原始字符串的char[]数组（而不是创建一个新的数组），具有不同的偏移量和长度。由于StringBuilder是可变的，因此无法对substring的StringBuilder版本执行此操作，使其速度略慢。然而，在较新版本的Java中，共享字符数组的整个方案已经被大量放弃。 - Hot Licks

Answer 2

最有效的方法是使用char数组。然而，它不会像创建String对象一样显著。

String s = "foobarbaz"; 
char[] cha = s.toCharArray();
int length = cha.length;
String[] suffixes = new String[length];
for (int i = 0; i < length; ++i)
  suffixes[i] = new String(cha, i, length-i);

- Danstahr

Answer 3

你可以这样做，避免使用子字符串方法。

public String[] suffix(String s)
{
    String[] suffixes = new String[s.length()];
    String suffix = null;
    for (int i = 0 ; i < s.length() ; i++)
    {
        suffix = suffix == null ? "" + s.charAt(i) : suffix + s.charAt(i);
        suffixes[i] = suffix;
    }

    return suffixes;
}

不确定它是否更快。

- The Cat

---

这实际上计算前缀而不是后缀，我认为我会把答案留在这里，因为楼主可能会觉得有用，但如果您希望的话，我可以将其删除。 - The Cat

没关系，我有点误解了。 - catch23

Answer 4

在完成此任务时，您始终需要 n + 1 个字符串。唯一可以优化的是创建这些对象的时间。

您可以将字符串表示形式创建为 char 数组，并延迟（按需）返回后缀。

您可以使用 Iterable 和 Iterator 接口来实现：

public class StringSufixies implements Iterable<String> {

    private final String input; 

    public StringSufixies(String input) {
        this.input = input;
    }

    @Override
    public Iterator<String> iterator() {
        return new SuffixStringIterator(input);
    }

    private static class SuffixStringIterator implements Iterator<String> {

        private final String input;
        private final int size;
        private int suffixId;

        private SuffixStringIterator(String input) {
            this.input = input;
            this.size  = input.length();
            this.suffixId = 1;
        }

        @Override
        public boolean hasNext() {
            return suffixId <= size;
        }

        @Override
        public String next() {
            return input.substring(0, suffixId++); //At this point we create new String
        }

        @Override
        public void remove() {
            //Add throw or other impl
        }

    }

}

你可以在一个字符数组上实现关键功能。

private static class SuffixCharIterator implements Iterator<String> {

private final char[] charSequence;
private final int size;
private int suffixId = 0;

private SuffixCharIterator(char[] charSequence) {
    this.charSequence = charSequence;
    this.size = charSequence.length;
}

@Override
public boolean hasNext() {
    return suffixId <= size;
}

@Override
public String next() {
    return new String(charSequence, 0, suffixId++); //At this point we create a new String
}

@Override
public void remove() {

}

}

但是在我看来，这更加复杂，而且我们并没有获得任何好处。

这种解决方案的优点是，您可以处理结果并决定在创建所有前缀之前停止。

- Damian Leszczyński - Vash

Answer 5

你的代码片段唯一的区别就是使用了String或StringBuilder，而且你只是用它来检索子字符串。
subString()从StringBuilder中实现。

 new String(offset + beginIndex, endIndex - beginIndex, value);  

从字符串中使用subString()方法

 new String(offset + beginIndex, endIndex - beginIndex, value);  

两者都是相同的，都会创建一个新的字符串，因此在性能上不会有任何区别。

- Ajinkya