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，导致超时错误而失败

在这篇文章中也有类似的问题-{a1}我也用了同样的答案

解决这个问题的正确方法是什么

Answer 1

不过，有些想法可能不足以解决您的可伸缩性问题：

1. 您不需要if (!set.contains(elem))检查，因为这已经在set.add()方法的逻辑中了。这需要一些时间来检查（即使是常数）

2. 您可能希望将集合更改为列表（即使这涉及更大的空间消耗），并在最后转换为集合，以删除重复项

3. 似乎有些计算可以并行进行（例如，分配给一个工人执行长度为1的子串，分配给另一个长度为2的子串，等等）。这些不需要交叉检查（即，不需要检查每个工人的结果是否重复）。例如，您可以尝试多线程或Spark（如果并行化开销没有更大的话）

Answer 2

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

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

我们可以看到，每个后缀p[i]都有长度n - p[i]，并产生n - p[i]前缀作为子字符串。但是lcp[i-1]前缀与前一个后缀的前缀重合！因此，对于每个后缀，我们只有n - p[i] - lcp[i-1]个新的inique子字符串。通过siffixes获得O（n）时间内不同子字符串的计数

总的时间是

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

Answer 3

从GeeksForGeeks尝试这个解决方案

public class GFG { 
    Set<String> set = new HashSet<String>();
    public static void SubString(String str, int n) 
    { 
        for (int i = 0; i < n; i++)  
            for (int j = i+1; j <= n; j++) 
                set.add(str.substring(i, j)); 
    } 

    public static void main(String[] args) 
    { 
        String str = "abcd"; 
        SubString(str, str.length()); 
    } 
}