4

我正在寻找在 Java 中制作后缀数组的方法。
我发现了两种能力变体。此外，我想更深入地了解这些变体之间的差异。
包括 running time& space。

代码（后缀）：

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

问题：

  • 如何有效地形成后缀数组？
4

5 回答 5

3

您描述的两种执行方式之间没有明显的区别：由于StringJava中的 s 是不可变的，因此将为每个后缀创建一个新对象。与设置新字符串对象所需的分配和复制相比，从Stringvs.创建子字符串不会给您带来太大的性能差异。StringBuilder

当您查找后缀时，不需要传递结束索引：使用采用单个的重载int代替：

for (int i = 0; i < N; i++)
    suffixes[i] = s.substring(i);
于 2013-04-16T11:27:28.437 回答
0

您的代码片段之间的唯一区别是使用 String 或 StringBuilder，您也仅使用它来检索子字符串。
subString()从 StringBuilder 做

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

subString()从 String 开始

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

两者都相同并创建新字符串，因此性能不会有任何差异

于 2013-04-16T11:30:40.087 回答
0

你可以这样做，这避免了 substring 方法，

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

不确定它是否更快。

于 2013-04-16T11:39:32.623 回答
0

最后，您总是需要 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
        }

    }

}

您可以通过 char 数组实现关键功能。

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() {

}

}

但恕我直言，更复杂，我们一无所获。

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

于 2013-04-16T12:27:05.070 回答
0

最有效的方法是使用 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);
于 2013-04-16T11:37:39.277 回答