生成给定字符串的所有唯一子字符串

Question

给定一个string s，生成一组所有唯一子字符串的最快方法是什么？

示例：因为str = "aba"我们会得到substrs={"a", "b", "ab", "ba", "aba"}。

天真的算法是遍历整个字符串，1..n在每次迭代中生成长度的子字符串，从而产生一个O(n^2)上限。

更好的约束可能吗？

（从技术上讲这是家庭作业，因此也欢迎只使用指针）

Answer 1

正如其他张贴者所说的，给定字符串可能有O（n ^ 2）个子字符串，因此将它们打印出来的速度不能比这快。但是，存在可以在线性时间内构建的集合的有效表示形式：后缀树。

Answer 2

这样做没有比O（n 2）快的方法，因为一个字符串中总共有O（n 2）个子字符串，因此，如果必须全部生成它们，则它们的数量将是n(n + 1) / 2最坏的情况，因此上下限的为O（n 2） Ω（N 2）。