Есть задача timus1590. Проще говоря надо найти кол-во различных подстрок в строке. Было бы интересно услышать решение быстрее, чем O(n*n), если оно существует =).
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Название |
---|
O(NlogN)
Можно решать за:
O(nlogn). Построим суффиксный массив, а вместе с ним — массив lcp, в котором будем обозначать длины наибольших общих префиксов соседних в массиве суффиксов. Тогда ответ будет таким:![](/predownloaded/e3/75/e37556871b9208ce2b30bb4038b280462fdc49f9.png)
Подробнее о суффиксном массиве можно почитать на e-maxx.
O(n). Суффиксное дерево или суффиксный автомат. Можно заметить, что различные подстроки = различные пути в этих структурах. В суффиксном дереве (в "разжатом" виде) каждой подстроке будет соответствовать одна вершина. Значит, мы можем пройтись по всем рёбрам сжатого суффиксного дерева и добавлять к ответу last - first этого ребра. В суффиксном автомате можно явно посчитать кол-во путей динамикой с dfs'ом, а можно заметить, что суфф ссылки образуют суффиксное дерево перевёрнутой строки и сложить символы, которые они охватывают. Это тоже даст верный ответ.
P.S.
Строить суффиксный массив можно за O(N), искать lcp соседних суффиксов тоже — алгоритм Касаи. Почему O(NlogN)?
В принципе, можно. Но лично я не умею этого и не знаю, насколько это оправданно в плане отношения сложности написания алгоритмов и реального выигрыша во времени работы. Буду рад, если раскроешь тему.
На хабре неплохо написано.
Кстати, это, возможно, интересно. Суффиксное дерево можно построить за O(n), если иметь суффиксный массив и массив lcp. Правда, в оффлайне...
а правда, что dfs по суфдереву -> суфмас?
Ага.
Ну, если мы переходы в нём по алфавиту сортируем, а не рандомно храним.
на хабре написано про алгоритм 10-летней давности, который уже множество раз улучшили.
Сейчас есть два основных алгоритма построения суффиксного массива:
SA-IS и его улучшенная версия SACA-K, не требующая дополнительной памяти — O(n), на практике работают в 4-5 раз быстрее того, что описано у е-макса. страница автора
DivSufSort.
. Во всех статьях пишут, что работает еще в 1.5-2 раза быстрее предыдущего алгоритма, но код поистине ужасен.
Они работают быстрее на практике или для worst-case? Это разные вещи.
для SACA-K в худшем случае длина сортируемой строки на каждой итерации уменьшается в 2 раза. Проверял на строках Фибоначчи, которые близки к этому (на каждой итерации получается переход от n-й к (n-2)-й строке Фибоначчи) — все равно работает в разы быстрее qsufsort.
про DivSufSort ничего не могу сказать, кроме того что написано здесь
double post
Delete