java - Java 中的字符串子串生成

Question

我正在尝试查找给定字符串中的所有子字符串。对于像 rymis 这样的随机字符串，子序列将是 [i, is, m, mi, mis, r, ry, rym, rymi, rymis, s, y, ym, ymi, ymis ]。来自 Wikipedia ，长度为 n 的字符串将有 n * (n + 1)/2 个子字符串。

可以通过执行以下代码片段找到:

    final Set<String> substring_set = new TreeSet<String>();
    final String text = "rymis";

    for(int iter = 0; iter < text.length(); iter++)
    {
        for(int ator = 1; ator <= text.length() - iter; ator++)
        {
            substring_set.add(text.substring(iter, iter + ator));
        }
    }

它适用于较小的字符串长度，但由于算法接近 O(n^2)，因此对于较大的长度显然会变慢。

还阅读了可以在 O(n) 中插入的后缀树，并注意到可以通过从右边删除 1 个字符直到字符串为空来重复插入子字符串来获得相同的子序列。这应该是关于 O(1 + … + (n-1) + n) 这是一个 n 的总和 -> n(n+1)/2 -> (n^2 + n)/2，这又接近 O(n^2)。虽然似乎有一些后缀树可以在 log2(n) 时间内进行插入，但如果是 O(n log2(n)) 则更好。

在我深入研究后缀树之前，这是要采取的正确路线吗？是否有其他算法对此更有效，或者 O(n^2) 是否与此一样好会得到吗？

Answer 1

我相当确定您不能为此打败 O(n^2)，正如对问题的评论中提到的那样。

我对不同的编码方式很感兴趣，因此我很快制作了一个，并决定将其发布在这里。

我认为我放在这里的解决方案并没有渐进地更快，但是当计算内部和外部循环时，它会更少。这里也有较少的重复插入 - 没有重复插入。

String str = "rymis";
ArrayList<String> subs = new ArrayList<String>();
while (str.length() > 0) {
    subs.add(str);
    for (int i=1;i<str.length();i++) {
        subs.add(str.substring(i));
        subs.add(str.substring(0,i));
    }
    str = str.substring(1, Math.max(str.length()-1, 1));
}