我正在解决与 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 .
最佳答案
如果我们有 N
个单词,每个单词的最大长度为 L
,您的算法将采用 O(N*L^3)
(假设添加到 trie 与添加单词的长度成线性关系)。但是,生成的 trie 的大小(节点数)最多为 O(N*L^2)
,因此看起来您是在浪费时间,您可以做得更好。
确实可以,但是您必须从袖子里拿出一些技巧。此外,您将不再需要 trie。
.substring()
恒定时间
在 Java 7 中,每个 String
都有一个支持 char[]
数组以及起始位置和长度。这允许 .substring()
方法在恒定时间内运行,因为 String
是不可变类。创建了具有相同后备 char[]
数组的新 String
对象,只是起始位置和长度不同。
您需要稍微扩展一下,以通过增加长度来支持在字符串末尾添加。总是创建一个新的字符串对象,但保持后备数组不变。
- 附加单个字符后在常数时间内重新计算散列
同样,让我为 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 的幂,也可以使用其他素数。
- 将所有子字符串存储在单个
HashMap
使用技巧 1 和技巧 2,您可以在 O(N*L^2)
时间内生成所有子字符串,这是子字符串的总数。总是从长度为 1 的字符串开始,一次添加一个字符。将所有字符串放入一个 HashMap 中,以减少重复。
(你可以在排序时/排序后跳过2和3并丢弃重复项,也许它会更快。)
- 对子字符串进行排序,一切顺利。
好吧,当我到达第 4 点时,我意识到我的计划行不通,因为在排序时您需要比较字符串,这可能需要 O(L)
时间。我想出了几个尝试来解决它,其中包括桶排序,但没有一个比原来的更快 O(N*L^3)
我会在这里回答这个问题,以防它能激发某人的灵感。
万一你不知道Aho-Corasic algorithm ,看看它,它可能对您的问题有一些用处。
关于algorithm - 优化所有子字符串的 trie 结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31166558/