我正在学习如何从给定字符串生成后缀树的Ukkonen算法。我在可视化网站http://brenden.github.io/ukkonen-animation/中尝试了一个字符串"dedododeodo“，我不完全理解的一件事是:为什么从节点编号8到节点编号3没有任何后缀链接我的理
浏览 31提问于2021-07-19得票数 1
最近，我正在学习如何使用树来解决最长的常见子串问题。在学习了Wiki和其他在线资源之后，我发现我们应该使用后缀树来查找最长的公共子字符串。正如维基所说：
一组字符串中最长的公共子字符串可以通过为字符串构建一个通用后缀树来找到，然后从它下面的子树中的所有字符串中找到具有叶节点的</em
浏览 7提问于2014-09-23得票数 2
回答已采纳
9回答
我天真地想象着，我可以构建一个后缀trie，在这里我为每个节点保留一个访问计数，然后我正在寻找的结果集是计数大于一个的最深节点。
存
浏览 7提问于2008-12-29得票数 11
回答已采纳
2回答
给定长度为s的字符串n，可以在O(n)中计算s中不同子字符串的数目吗？我知道O(n^2)方法是可能的，但是有更有效的算法吗？
我不需要获取每个子字符串，只需要获得不同子字符串的总数(以防有差异)。
浏览 1提问于2016-01-19得票数 8
回答已采纳
1回答
文献中的估计数字对我来说是很高的。
每株树的平均分枝因子为: 80 40 8 3 2 1 1.也就是说，只有树的前3-5层实际上是树枝。我更好地构建3-5层和保持长文本后缀节点。在对15 10文本的进一步实验中，在添加前10,000个后缀(长到短)后，我耗尽了2Gb的内存。几乎没有重复的子字符串</em
浏览 12提问于2018-01-13得票数 0
1回答
我很难理解构建后缀树最糟糕的时间复杂度是如何线性的--特别是当我们需要为一个字符串构建后缀树时，该字符串可能由重复单个字符(如"aaaaa“)组成。即使我要为"aaaaa“构造一个压缩的后缀树，我也不能真正地压缩任何节点，因为从节点开始的任何两个边都不能有以相同字符开头<e
浏览 2提问于2015-07-23得票数 5
我遇到了一个问题，它需要一个包含字符串S的数据结构，并允许我：
我发现由Ukkonen算法构造的是我正在寻找的。算法被描述为，而我的“在线”部分有一
浏览 3提问于2013-01-11得票数 3
回答已采纳
1回答
在后缀树中遍历
、、、、
我用java语言创建了一个后缀树。我们知道后缀树的应用之一是从树中搜索字符串。所以我的问题是，我如何遍历后缀树的每个节点来查找后缀树中是否存在搜索字符串。
提前谢谢你。
浏览 4提问于2014-04-02得票数 0
6回答
我正在读一篇关于Tries的文章，通常被称为前缀树和Suffix Trees。这是真的吗？有没有人能帮我理清头绪？一个示例代码将会很有帮助！
浏览 0提问于2012-12-16得票数 86
回答已采纳
我试图使用ukkonen的后缀树来比较文档。
我能够为基于的文档生成ukkonen后缀树。并
浏览 0提问于2014-01-29得票数 2
1回答
我有一个大约10年的归档文件，这是一个大的目录树结构，在较大的树中的不同位置有较小尝试的多个副本。由于缺乏一致的备份策略和归档策略(基本上都是我自己的错)，这棵树变成了这样的结构。我正在寻找一种在更大的树中找到完全相同的树副本的方法，这样我就可以删除不需要的
浏览 0提问于2013-03-03得票数 0
我们需要在两个字符串之间找到最短的不寻常子串，也就是说，如果我们有两个字符串，a和b，那么我们需要找到a的最短子字符串的长度，它不是b的子字符串。
如何使用后缀数组来解决这个问题？求解的复杂度不超过n*lg(n)
浏览 2提问于2012-09-26得票数 11
回答已采纳
1回答
我构造了一个后缀trie，这是一个包含字符串所有后缀的树，其中每个节点只包含一个字符，在每个路径的末尾有一个SuffixNode，其中包含后缀在字符串中的位置。假设我的trie包含单词"Cat“、"Car”和"Can“，并且我想搜索"Ca"，结果应该返回3<em
浏览 1提问于2012-03-17得票数 3
回答已采纳
云服务器
ICP备案
云直播
对象存储
实时音视频
腾讯云开发者
