给定一个string s,生成一组所有唯一子字符串的最快方法是什么?
s
示例:因为str = "aba"我们会得到substrs={"a", "b", "ab", "ba", "aba"}。
str = "aba"
substrs={"a", "b", "ab", "ba", "aba"}
天真的算法是遍历整个字符串,并1..n在每次迭代中生成长度的子字符串,从而产生O(n^2)上限。
1..n
O(n^2)
更好的约束可能吗?
(从技术上讲这是家庭作业,因此也欢迎只使用指针)
正如其他张贴者所说的,给定字符串可能有O(n ^ 2)个子字符串,因此将它们打印出来的速度不能比这快。但是,存在可以在线性时间内构建的集合的有效表示形式:后缀树。