Блог

У меня есть последовательность значений, и я хочу знать, содержит ли она повторяющиеся подпоследовательности определенной минимальной длины. Например:

 1, 2, 3, 4, 5, 100, 99, 101, 3, 4, 5, 100, 44, 99, 101
  

Содержит подпоследовательность 3, 4, 5, 100 дважды. Он также содержит подпоследовательность 99, 101 дважды, но эта подпоследовательность слишком коротка, чтобы о ней заботиться.

Существует ли эффективный алгоритм для проверки существования такой подпоследовательности? Меня не особенно интересует расположение последовательностей (хотя это было бы полезно для проверки), меня в первую очередь интересует ответ True / False, учитывая последовательность и минимальную длину подпоследовательности.

Мой единственный подход на данный момент заключается в переборе методом грубой силы: для каждого элемента в последовательности найдите все другие местоположения, где этот элемент встречается (уже в O (N ^ 2)), а затем продвигайтесь по одному шагу за раз из каждого местоположения и смотрите, совпадает ли следующий элемент, и продолжайте, пока я не найду несоответствие или соответствующую подпоследовательность достаточной длины.

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

Существуют O(k) решения ( k — длина всей последовательности) для любого значения N .

Решение № 1:
Постройте дерево суффиксов для входной последовательности (используя алгоритм Укконена).
Выполните итерацию по узлам с двумя или более дочерними элементами и проверьте, имеет ли хотя бы один из них глубину >= N .

Решение № 2:
Создайте суффиксный автомат для входной последовательности.
Выполните итерацию по всем состояниям, правый контекст которых содержит по крайней мере две разные строки, и проверьте, удален ли хотя бы один из этих узлов >= N от начального состояния автомата.

Решение № 3: Также можно использовать
массив суффиксов и метод самого длинного общего префикса (построить массив суффиксов для входной последовательности, вычислить самый длинный общий префиксный массив, проверить, достаточно ли пары смежных элементов с общим префиксом длиной не менее N ).

Эти решения имеют O(k) временную сложность в предположении, что размер алфавита постоянен (алфавит состоит из всех элементов входной последовательности).
Если это не так, все равно можно получить O(k log k) временную сложность в наихудшем случае (путем сохранения всех переходов в дереве или в автомате в map ) или O(k) в среднем с использованием hashmap .

P.S Здесь я использую термины string и sequence взаимозаменяемо.

Если вас интересуют только подпоследовательности длиной ровно N (например, если вы просто хотите проверить, что дубликатов нет), то есть квадратичное решение: используйте алгоритм KMP для каждой подпоследовательности.

Давайте предположим, что во всей последовательности есть k элементов.

Для каждой подпоследовательности длиной N (O (k) из них):

• Создайте его функцию сбоя (принимает O (N))
• Найдите его в оставшейся части последовательности (занимает O (k))

Итак, предполагая, что N << k, весь алгоритм действительно равен O (k ^ 2).

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

Я думаю, что сначала вы просматриваете свой список и создаете словарь, где вы сохраняете число в качестве ключа вместе со всеми индексами, которые оно появляется в вашей последовательности. Нравится:

 Key: Indices
  1: 0 
  2: 1 
  3: 2, 8
  ....
  

Где число 1 появляется в индексе 0, число 2 появляется в индексе 1, число 3 появляется в индексах 2 и 8, и так далее.

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