java - 获取所有唯一的子字符串

Question

我正在开发一个程序，该程序计算给定输入字符串的所有可能的不同连续子字符串。

这是我的程序:

public int getAllUniqueSubset(String str) {
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length() - i; j++) {
                String elem = str.substring(j, j + (i+1));
                if (!set.contains(elem)) {
                    set.add(elem);
                }
            }
        }
        return set.size();
    }

现在，当我在几天前的在线考试中使用它时，它因超时错误而失败，因为输入字符串长度最多可达 10 的 5 次方。

这篇文章中也提出了类似的问题 - finding all distinct substring of a string另外，我使用了相同的答案。

解决这个程序的正确方法是什么？

Answer 1

字符串长度 10^5 假设二次求解太慢。您生成所有 n^2 子字符串并计算它们的哈希值，因此总体时间是立方的，并且超时是可预期的。

相反，您可以在 O(nlogn) 时间内构建后缀数组，然后使用 Kasai 方法或其他算法构建 LCP(最长公共(public)前缀)。

我们可以看到每个后缀 p[i] 的长度都是 n - p[i] 并产生 n - p[i]前缀作为子字符串。但是lcp[i-1]前缀与前一个后缀的前缀一致!因此，对于每个后缀，我们只有 n - p[i] - lcp[i-1] 新的唯一子字符串。遍历后缀并在 O(n) 时间内获取不同子字符串的计数。

总时间为

O(nlogn) (suffix array) + 
O(n) (Kasai LCP) + 
O(n) for counting = 
   O(nlogn)