Поиск циклических строк

Question

Я ищу наиболее эффективный способ хранения двоичных строк в структуре данных (функция вставки), а затем при получении строки я хочу проверить, есть ли какая-либо циклическая строка данной строки в моей структуре.

Я думал о сохранении входных строк в Trie, но затем, когда пытался определить, была ли какая-то циклическая строка строки, которую я получил, была вставлена ​​в Trie, это означает выполнить | s |ищет в Trie все возможные циклические строки.

Есть ли способ сделать это более эффективно, пока сложность места будет такой же, как в Trie?

Примечание: Когда я говорю циклические строки строки, я имею в виду, что, например, все циклические строки 1011: 0111, 1110, 1101, 1011

Answer 1

Можете ли вы придумать канонизирующую функцию для циклических строк, основанную на следующем:

1. Найдите наибольший ряд нулей.
2. Поверните строку так, чтобы этот ряд нулейнаходится впереди.
3. Для каждого прогона нулей одинакового размера, посмотрите, если вращение на фронт приводит к лексикографически меньшей строке, и если это так, используйте это.

Это канонизируетвсе в классе эквивалентности (1011, 1101, 1110, 0111) до лексикографически наименьшего значения: 0111.

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

Затем вы можете хешировать на основе канонической формы или использовать три, которая будет включать только пустую строку и строки, начинающиеся с 0, и один прогон трия.ответит на ваш вопрос.

РЕДАКТИРОВАТЬ:

, если у меня есть строка длины | s |Чтобы найти наименьшее лексикографическое значение, может потребоваться много времени. Сколько времени на самом деле это займет?

Вот почему я сказал, что 010101.... - это значение, для которого оно плохо работает.Скажем, строка имеет длину n, а самая длинная последовательность из 1 имеет длину r.Если биты распределены случайным образом, длина самого длинного прогона равна O (log n) согласно «Распределение самого длинного прогона» .

Время поиска самого длинного прогона равно O (п).Вы можете реализовать сдвиг, используя смещение вместо буферной копии, которая должна быть O (1).Количество прогонов - наихудший случай O (n / m).

Тогда время выполнения шага 3 должно быть

1. Найти другие длинные прогоны: один O (n) проходс O (log n) среднего значения хранения, O (n) наихудшим случаем
2. Для каждого прогона: O (log n) среднего случая, O (n) наихудшим случаем
3. Сдвиг и сравнение лексикографически: O (log n) средний случай, так как большинство сравнений случайно выбранных строк терпят неудачу рано, O (n) худший случай.

Это приводит к худшему случаю O (n²), но средний случайO (n + log² n) ≅ O (n).

Answer 2

У вас есть n строк s1..sn и дана строка t, которую вы хотите узнать, является ли циклическая перестановка t подстрокой любого s1..sn.И вы хотите хранить строки максимально эффективно.Правильно ли я понял ваш вопрос?

Если да, то здесь есть решение, но с большим временем выполнения: для заданного ввода t пусть t '= concat (t, t), проверьте t' с помощьюкаждый s в s1..sn, чтобы увидеть, является ли самая длинная подпоследовательность t 'и sm не меньше | t |Если | Си |= k, | t |= l он работает за O (нкл) времени.И вы можете хранить s1..sn в любой структуре данных, которую вы хотите.Это достаточно хорошо или вы?