структура данных для строк сдвига - PullRequest
Новая
       11

структура данных для строк сдвига

1 голос
/ 20 января 2012

Нас интересует структура данных для двоичных строк.Пусть S = s 1 s 2 .... s m - двоичная строка размером m.Shift(S,i) - циклический сдвиг строки S i влево.То есть Shift (S, i) = s i s i + 1 s i + 2 ... s m s 1 ... s я-1 .Предложить эффективную структуру данных, которая поддерживает:

  1. Init() empy DS в O (1)
  2. Insert(s) вставляет двоичную строку в DS в O (| s| ^ 2)
  3. Search_cyclic(s) проверяет, есть ли Shift(S,i) для ЛЮБОГО i в O (| s |).

Сложность пространства: O (| S 1 | + | S 2 | + ..... + | S m |) где S i - единица, еслиm строк, которые мы вставили так далеко.

Если мне нужно было найти Search_cyclic (s, i) для некоторого заданного i, это довольно просто с использованием дерева суффиксов и просто обходом его в O (| s |).Но здесь в Search_cyclic (s) у нас нет данного i, поэтому я не знаю, что делать в данной сложности.OTOH, Insert (s) обычно использует O (| s |) для вставки в дерево суффиксов, и здесь нам дается O (| s | ^ 2).

1 Ответ

0 голосов
/ 23 января 2012

Итак, вот решение, которое я могу предложить вам.Сложности даже ниже, чем те, о которых они вас просили, но это может показаться немного сложным.

Структура данных, в которой вы сохраняете все строки, будет Trie или даже Патриция дерево .В этом дереве для каждой строки вы хотите вставить минимальный циклический сдвиг (т.е. циклический сдвиг всех возможных, который является минимальным лексикографически) из всех его возможных сдвигов.Вы можете рассчитать минимальный циклический сдвиг строки в линейном времени, и я дам одно возможное решение этого чуть позже.На данный момент давайте предположим, что вы можете сделать это.Вот как будут реализованы требуемые операции:

  1. Init () - init как дерева trie, так и дерева patricia является постоянным - здесь нет проблем
  2. Insert (s) - вы вычисляетеминимальный циклический сдвиг s ​​'s в O (| s |), а затем вы вставляете его в любую из структур данных в O (| s' |) = O (| s |).Это даже лучше, чем требуемая сложность
  3. Search_cyclic (s) - снова вы вычисляете минимальный циклический сдвиг s ​​в O (| s |) и затем проверяете в Патрисии или Три, если строка присутствует,что снова делается в O (| s |)

Также сложность памяти такая же, как требуется, и может быть даже ниже, если вы создаете Патрицию.

Так что все, что осталось, этообъяснить, как найти минимальный циклический сдвиг.Поскольку вы упоминаете суффиксное дерево, я надеюсь, что вы знаете, как его построить за линейное время .Итак, хитрость в том, что вы добавляете свою строку s к себе (т.е. удваиваете ее), а затем создаете дерево суффиксов для удвоенной строки.Это все еще линейно относительно | s |так что никаких проблем нет.После этого все, что вам нужно сделать, это найти минимум суффиксов длины n в этом дереве.Я полагаю, что это совсем не сложно - начинайте с корня и всегда переходите по ссылке с текущего узла, на котором написана минимальная строка, пока вы не наберете длину больше, чем | s |.Из-за удвоения строки вы всегда сможете следовать минимальным строковым ссылкам, пока не наберете длину не менее | s |.

Надеюсь, этот ответ поможет.

...