优化构建所有子字符串的Trie树

Question

我正在解决一个trie相关的问题。有一个字符串集合S。我要为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的复杂度？

为什么需要这样做？因为我正在尝试解决这个问题。

- Bhoot

Answer 1

您可能需要的是后缀自动机。它只需O(n)的时间就能识别所有子串。 后缀数组也可以解决这些问题。

这两种算法可以解决大多数字符串问题，但它们确实很难学习。一旦您学会了，您就能解决它们。

- newSolar

Answer 2

如果我们有N个单词，每个单词的最大长度为L，那么你的算法将花费O(N*L^3)的时间（假设添加到trie中是与添加单词的长度成线性关系）。然而，生成的trie的大小（节点数）最多为O(N*L^2)，所以看起来你浪费了时间，可以做得更好。

实际上，你确实可以做到更好，但需要从袖子里拿出一些技巧。此外，你将不再需要trie。

1.常数时间内使用.substring()

在Java 7中，每个字符串都有一个后备的char[]数组，以及起始位置和长度。这使得.substring()方法可以在常数时间内运行，因为String是一个不可变类。创建一个新的String对象，只是用不同的起始位置和长度，但是共用相同的char[]数组。

你需要稍微扩展一下这个方法，在字符串末尾添加字符。总是创建一个新的字符串对象，但保持相同的char[]数组。

在追加单个字符后，在常数时间内重新计算哈希值。

再次，让我使用Java中的String的hashCode()函数：

int hash = 0;
for (int i = 0; i < data.length; i++) {
    hash = 31 * hash + data[i];
} // data is the backing array

现在，如果在单词末尾添加一个字符，哈希会如何改变？很简单，只需添加它的值（ASCII代码）乘以31^length。您可以将31的幂保留在某个单独的表中，也可以使用其他质数。

使用技巧1和2，您可以在时间O(N*L^2)内生成所有子字符串，这是子字符串的总数。只需始终从长度为一的字符串开始，每次添加一个字符。将所有字符串放入单个HashMap中，以减少重复。

（您可以跳过2和3，在排序时/之后丢弃重复项，也许速度会更快。）

对子字符串进行排序，然后您就可以开始了。

嗯，当我到达第4点时，我意识到我的计划行不通，因为在排序时需要比较字符串，这可能需要O(L)的时间。我想出了几种解决方法，其中包括桶排序，但没有一种比原始的O(N*L^3)更快。

我会把这个答案放在这里，以防它能激励到某人。

---

如果您不知道Aho-Corasic算法，可以了解一下，它可能对您的问题有所帮助。

- kajacx

---

我听说过这个算法，看完后再回复你。我不确定它是否适合解决这个问题。 - Bhoot

我刚意识到这个答案是错误的，请等一分钟直到我重写它。 - kajacx

Answer 3

首先，注意只需向Trie树添加后缀即可，每个子字符串的节点将在此过程中添加。

其次，您需要压缩Trie树，否则它将不适合HackerRank规定的内存限制。此外，这还会使您的解决方案更快。

我刚提交了实现这些建议的解决方案，它被接受了。（最大执行时间为0.08秒。）

但是，你可以通过实现线性时间算法来构建后缀树，使你的解决方案更快。你可以在这里和这里阅读关于线性时间后缀树构造算法的文章。在StackOverflow上也有Ukkonen算法的解释这里。

- dened

Answer 4

您可以考虑以下优化：

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

但是，将所有子字符串插入trie树的最坏情况复杂度将达到n^2级别，其中n是字符串数组的大小。从问题页面上看，这相当于在trie树中进行10^8次插入操作。因此，即使每个插入平均需要10个操作，总共也会有10^9个操作，这将导致超出时间限制。

问题页面将LCP数组称为与问题相关的主题。您应该考虑改变方法。

- n00bc0d3r

---

我并不是在居高临下地说话，但考虑到你的用户名，这个回答还是挺讽刺的。 :) - Bhoot

@Bhoot：哈哈！不会有任何冒犯。 - n00bc0d3r

我建议将添加的子字符串集合实现为某种形式的“哈希集”，因为您可以在添加或删除单个字母时以常数时间重新计算字符串的哈希值。 - kajacx