Блог пользователя 1k_trash

Автор 1k_trash, 11 лет назад, По-русски

Всем привет!

Дана строка длины 10^5, нужно найти такую её подстроку, которая повторяется подряд максимальное количество раз (и если таких несколько -- выбрать самую длинную/короткую/лексикографически_какую_нибудь).

Например тест bacacacb должен дать ответ ac.

Как решать такое? Спасибо.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Задача на этот пост.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо, но это немного не то.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Вроде как нет, там нужен префикс, а тут подстрока, насколько я понимаю, в произвольном месте. Например тест bacacacb должен дать ответ ac

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, вы правы, подстрока в произвольном месте, а не префикс.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://e-maxx.ru/algo/prefix_function сжатие строки

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Почему-то сначала показалось, что должно сводиться как-то очевидно.
    Кажется, с помощью этого алгоритма можно за 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)), но он, похоже, сложнее Мейна-Лоренца.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ошибка, не прочитал, что подряд :)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вроде суффиксным автоматом можно, если в каждом состоянии хранить количество таких строк. Если нельзя поправьте меня.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мб суффиксным деревом как-нибудь?

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      По-моему там и автомата хватит, если учесть что он быстро пишется и ест O(N) памяти, то вполне подойдет для этой задачи

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    aclwawalaciac
    Your solution will give ac as an answer, but the correct answer is wa.
    It seems that you didn't notice "such substring that repeats one after another maximum number of times"

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

Алгоритм Дюваля + Z- функция если требуется найти лексикографически наименьшую подстроку и количество ее вхождений

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

i have an idea but i need to check it first, can you please give the problem link?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't have a link to this problem at online-judge, it is from some past on-site contest.