@lexstile

Как решить задачу?

Есть массив:
[1, 2, 3, 4, 5, 6, 2, 3, 4, 2, 3, 4];
В нем элементы с индексами 6-8 совпадают с 9-11.
Необходимо найти подобные последовательности и вывести в текущем случае: 2, 3, 4
  • Вопрос задан
  • 121 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Быстрое решение - построить для этого массива суффиксное дерево алгоритмом Укконена (или вот ссылка), потом обойти его, найти самую глубокую вершину, у которой есть более одного ребенка, и вывести путь до нее от корня. Работает за O(n).

Edit:

Вообще есть много решений разной заумности и скорости. Самое быстрое - за линию - я привел выше. Следующий уровень - за квадрат, через z-функцию (но пишется и понимается проще суффиксного дерева). Для каждого суффикса вашего массива найдите максимальное значение z-функции.

И еще проще, но уже за куб - переберите любые 2 позиции и потом одним циклом считайте, сколько символов с этих позиций совпадают.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы