优化所有子串的构造

Question

我正在解决一个与trie相关的问题.有一组字符串的小号.我必须为S中的每个字符串的所有子字符串创建一个trie .我使用以下例程:

String strings[] = { ... }; // array containing all strings
for(int i = 0; i < strings.length; i++) {
    String w = strings[i];
    for (int j = 0; j < w.length(); j++) {
        for (int k = j + 1; k <= w.length(); k++) {
            trie.insert(w.substring(j, k));
        }
    }
}

我正在使用此处提供的trie实现.但是,我想知道是否可以进行某些优化以降低在所有子串上创建trie的复杂性？

我为什么需要这个？因为我正在努力解决这个问题.

Answer 1

您可以考虑以下优化：

• 维护已处理子字符串的列表。插入子字符串时，检查处理后的集合是否包含该特定子字符串，如果是，则跳过在 trie 中插入该子字符串。

然而，在 trie 中插入所有子字符串的最坏情况复杂度将是 n^2 的量级，其中 n 是字符串数组的大小。从问题页面来看，这相当于 trie 中 10^8 次插入操作的顺序。因此，即使每次插入平均需要 10 次操作，总共也会有 10^9 次操作，这将使您超出时间限制。

问题页面将 LCP 阵列引用为该问题的相关主题。您应该考虑改变方法。