使用后缀树的唯一子串

提问于 2024-04-28T04:57:22+08:00

浏览次

1

对于给定字符串 S 长度 n -

用于查找 S 的所有唯一子串的最佳算法不能小于 O(n^2) . 因此，最好的算法将给我们 O(n^2) 的复杂性 . 根据我所读到的，这可以通过为 S 创建后缀树来实现 .

可以在 O(n) 时间创建S的后缀树 . 现在，我的问题是 -

How can we use the suffix tree for S to get all the unique substrings of S in O(n^2)?

2 回答

1

尝试阅读有关后缀数组的信息：http://en.wikipedia.org/wiki/Suffix_array此方法比后缀树更快，可以在字符串中获取子字符串 .

回复于 2024-04-28T04:57:22+08:00
2

它可以通过尝试最佳地完成 . 将字符串添加到trie并从根到遍历遍历 . 每个根节点路径将表示字符串的后缀 . 获取这些后缀的所有前缀 . 这些是独特的子串 .

回复于 2024-04-28T04:57:22+08:00

相关问题