@lexstile

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

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

Edit:

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

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

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

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