algorithm - 优化所有子字符串的 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 实现 here .但是，我想知道是否可以进行某些优化以降低在所有子字符串上创建 trie 的复杂性？

为什么我需要这个？因为我正在尝试解决 this problem .

Answer 1

如果我们有 N 个单词，每个单词的最大长度为 L，您的算法将采用 O(N*L^3)(假设添加到 trie 与添加单词的长度成线性关系)。但是，生成的 trie 的大小(节点数)最多为 O(N*L^2)，因此看起来您是在浪费时间，您可以做得更好。

确实可以，但是您必须从袖子里拿出一些技巧。此外，您将不再需要 trie。

1. .substring() 恒定时间

在 Java 7 中，每个 String 都有一个支持 char[] 数组以及起始位置和长度。这允许 .substring() 方法在恒定时间内运行，因为 String 是不可变类。创建了具有相同后备 char[] 数组的新 String 对象，只是起始位置和长度不同。

您需要稍微扩展一下，以通过增加长度来支持在字符串末尾添加。总是创建一个新的字符串对象，但保持后备数组不变。

1. 附加单个字符后在常数时间内重新计算散列

同样，让我为 String 使用 Java 的 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. 将所有子字符串存储在单个 HashMap

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

(你可以在排序时/排序后跳过2和3并丢弃重复项，也许它会更快。)

1. 对子字符串进行排序，一切顺利。

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

我会在这里回答这个问题，以防它能激发某人的灵感。

---

万一你不知道Aho-Corasic algorithm ，看看它，它可能对您的问题有一些用处。