Efficient All substring counting in sorted order

Question

You are given a string find the frequency of all substring sorted(decreasing order) according to there frequency.

Eg: ababa {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}.

output:

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

explanation

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

solution

1)one obvious solution is to keep all the string in hash map and count it frequency but it will take o(n^3logn) O(n^2 *n){n^2 number of substring *O(n) for comparision of string *logn(as map is maintened as Red black tree)} 2)Insert all substring in Ternary search tree then retrive frequency of each substring then sort the frequency O(n^3 logn)

I am wondering is there O(n^2) or O(nlogn) solution exsist.

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

Answer 1

An O(n^2) solution can be achieved in this way:

1. Insert all substrings into a trie. This can be done in O(n^2).

2. Obtain all frequency and sort them. Note that the frequency of any substring can only be in range [0, n], so a bucket sort can have all of the numbers sorted in O(n^2) since in the worst case there will be n^2 numbers.