1

你得到一个字符串，根据那里的频率找到所有排序（降序）的子字符串的频率。

例如：ababa {“a”、“b”、“a”、“b”、“a”、“ab”、“ba”、“ab”、“ba”、“aba”、“bab”、“aba "、"abab"、"baba"、"ababa"}。

输出：

3,2,2,2,2,1,1,1,1

解释

3 a 2 b 2 ba 2 aba 2 ab 1 abab 1 baba 1 ababa 1 bab

解决方案

1）一个明显的解决方案是将所有字符串保留在哈希图中并计算它的频率，但它需要 o(n^3logn) O(n^2 *n){n^2 个子字符串 *O(n) 进行比较字符串*logn（因为地图维护为红黑树）} 2）在三叉搜索树中插入所有子字符串，然后检索每个子字符串的频率，然后对频率进行排序O（n ^ 3 logn）

我想知道是否存在 O(n^2) 或 O(nlogn) 解决方案。

像这样http://www.quora.com/Given-a-string-how-do-I-find-the-number-of-distinct-substrings-of-the-string

4

1 回答 1

1

可以通过这种方式实现 O(n^2) 解决方案：

  1. 将所有子字符串插入到 trie 中。这可以在 O(n^2) 中完成。

  2. 获取所有频率并对它们进行排序。请注意，任何子字符串的频率只能在 [0, n] 范围内，因此桶排序可以使所有数字按 O(n^2) 排序，因为在最坏的情况下会有 n^2 个数字。

于 2015-06-09T19:38:06.290 回答