c# - 使用后缀树的唯一子串

Question

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

• S查找不能小于的所有唯一子串的最佳算法O(n^2)。所以，最好的算法会给我们带来O(n^2). 根据我所阅读的内容，这可以通过为S.

S的后缀树可以及时创建O(n)。现在，我的问题是——

我们如何使用 S 的后缀树来获取Sin的所有唯一子字符串O(n^2)？

Answer 1

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

Answer 2

它可以通过尝试以最佳方式完成。将字符串添加到 trie 并从根遍历到节点。每个根到节点的路径都将表示字符串的后缀。取这些后缀的所有前缀。这些是唯一的子字符串。