Эффективный Подсчет всех подстрок в отсортированном порядке

Question

Вам дают строку найти частоту всех отсортированных подстрок (в порядке убывания) в соответствии с их частотой.

Например: 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

Answer 1

Решение O(n^2) может быть достигнуто следующим образом:

1. Вставьте все подстроки в три. Это можно сделать за O(n^2).

2. Получить все частоты и отсортировать их. Обратите внимание, что частота любой подстроки может быть только в диапазоне [0, n], поэтому сортировка по сегментам может иметь все числа, отсортированные в O(n^2), так как в худшем случае будет n ^ 2 чисел.