Вам дается строка, которая определяет частоту всех отсортированных подстрок (в порядке убывания) в соответствии с их частотой.
Например: ababa {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba" "," абаб "," баба "," абаба "}.
вывод:
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) of string * 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
