| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Всем привет!
Дана строка длины 10^5, нужно найти такую её подстроку, которая повторяется подряд максимальное количество раз (и если таких несколько -- выбрать самую длинную/короткую/лексикографически_какую_нибудь).
Например тест bacacacb должен дать ответ ac.
Как решать такое? Спасибо.
Задача на этот пост.
Спасибо, но это немного не то.
Вроде как нет, там нужен префикс, а тут подстрока, насколько я понимаю, в произвольном месте. Например тест
bacacacbдолжен дать ответacДа, вы правы, подстрока в произвольном месте, а не префикс.
http://e-maxx.ru/algo/prefix_function сжатие строки
тоже самое
http://e-maxx.ru/algo/string_tandems
Почему-то сначала показалось, что должно сводиться как-то очевидно.
Кажется, с помощью этого алгоритма можно за O(n(log(n))2) решать так (решение не писал, мб оно неправильное):
В статье на e-maxx упоминаются тройки Крочемора — (начало,длина,максимальное количество повторений) и утверждается что таких троек O(nlog(n)). Описанный алгоритм Мейна-Лоренца находит однократные повторения, которые легко привести к парам (диапазон начал тандема, длина строки).
Преобразовывать такое представление в тройки Крочемора будем следующим образом:
Отдельно решим задачу для каждой длины L. Имеем набор из m диапазонов позиций начал тандемов длины L. Рассмотрим матрицу A размера L × n / L, такую, что ai, j = 1 только в случаях, когда в позиции jL + i в строке начинается тандем длины L, тогда тройкам Крочемора в этой матрице будут соответствовать горизонтальные непрерывные максимальные по включению отрезки из единиц. Сожмем эту матрицу, легко видеть, что каждый диапазон в этой матрице сожмется в не более чем 3 столбца и 3 строки. Теперь пройдемся вертикальной сканирующей прямой слева направо по матрице, поддерживая дерево отрезков со значениями элементов матрицы, которое умеет выполнять операции:
- присвоить единицу/ноль на отрезке
- найти первый ноль/единицу на отрезке
каждое появление 1 после 0 соответствует началу тройки, 0 после 1 — завершению тройки. Поэтому перед каждым присвоением проитерируемся по изменяющимся позициям и обновим тройки, к которым они относятся.
Таким образом, обработка тандемов одной длины выполняется за O(mlog(n)) операций, в сумме по всем длинам получится O(n(log(n))2). На нахождение каждой тройки тратится O(log(n)), поэтому итоговая сложность получится O(n(log(n))2).
P.S. можно конечно, применить алгоритм Крочемора, который найдет все тройки за O(n(log(n)), но он, похоже, сложнее Мейна-Лоренца.
На самом деле Крочеморовых троек $$$O(n)$$$.
https://www.mimuw.edu.pl/~rytter/TEACHING/TEKSTY/stacs2006.pdf
Ошибка, не прочитал, что подряд :)
Вроде суффиксным автоматом можно, если в каждом состоянии хранить количество таких строк. Если нельзя поправьте меня.
Мб суффиксным деревом как-нибудь?
По-моему там и автомата хватит, если учесть что он быстро пишется и ест O(N) памяти, то вполне подойдет для этой задачи
Спасибо!
Make a suffix array, and an LCP array. Now your task is to find the longest non-zero contiguous subsequence in the LCP array, which can easily be done in linear time.edit: sorry, I thought it just said maximum number of occurrences.
aclwawalaciacYour solution will give
acas an answer, but the correct answer iswa.It seems that you didn't notice "such substring that repeats one after another maximum number of times"
Алгоритм Дюваля + Z- функция если требуется найти лексикографически наименьшую подстроку и количество ее вхождений
i have an idea but i need to check it first, can you please give the problem link?
I don't have a link to this problem at online-judge, it is from some past on-site contest.