生成特定字符串的所有独特的子 [英] Generate all unique substrings for given string

问题描述

由于字符串取值，什么是最快的方法生成一组其所有的独特子的？

Given a string s, what is the fastest method to generate a set of all its unique substrings?

示例：海峡=ABA我们将获得 substrs = {A，B，AB，巴，阿坝} 。

天真的算法会遍历整个序列生成在每个迭代长度 1..1 子，产生了为O（n ^ 2）上限。

The naive algorithm would be to traverse the entire string generating substrings in length 1..n in each iteration, yielding an O(n^2) upper bound.

是一个更好的约束可能吗？

Is a better bound possible?

（这是技术上的功课，所以指针只，欢迎为好）的

推荐答案

至于其他的海报说，有可能为O（n ^ 2）子对于给定的字符串，所以打印出来，不能做得比这更快。然而存在该组的一个有效的重presentation，可以在线性时间来构成：后缀树的

As other posters have said, there are potentially O(n^2) substrings for a given string, so printing them out cannot be done faster than that. However there exists an efficient representation of the set that can be constructed in linear time: the suffix tree.

这篇关于生成特定字符串的所有独特的子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！