为给定的字符串生成所有唯一的子字符串 [英] Generate all unique substrings for given string

问题描述

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

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

示例:对于 str = "aba" 我们将得到 substrs={"a", "b", "ab", "ba", "aba"}.

Example: for str = "aba" we would get substrs={"a", "b", "ab", "ba", "aba"}.

最简单的算法是在每次迭代中遍历整个字符串，生成长度为 1..n 的子字符串，从而产生 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.

可能有更好的边界吗?

(这在技术上是家庭作业，所以也欢迎指针)

推荐答案

正如其他海报所说，给定的字符串可能有 O(n^2) 个子字符串，因此打印出来的速度不能比这更快.然而，存在可以在线性时间内构造的集合的有效表示:后缀树.

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屋！