小编典典

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

algorithm

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

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

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

更好的约束可能吗?

(从技术上讲这是家庭作业,因此也欢迎只使用指针)


阅读 534

收藏
2020-07-28

共1个答案

小编典典

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

2020-07-28