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

Question

[lexstile]

Есть массив:
[1, 2, 3, 4, 5, 6, 2, 3, 4, 2, 3, 4];
В нем элементы с индексами 6-8 совпадают с 9-11.
Необходимо найти подобные последовательности и вывести в текущем случае: 2, 3, 4

Comments

[Wataru]

Там еще элементы 3-4 совпадают с 6-7. Это тоже выводить, или вам самая длинная повторяющаяся последовательность нужна?

[lexstile]

wataru,

3-4 совпадают с 6-7

Скорей всего вы имели ввиду индексы - 2-3 и 5-6 (элементы: 3, 4)
Да, нужно найти самую большую последовательность.

Answer 1

[Wataru]

Быстрое решение - построить для этого массива суффиксное дерево алгоритмом Укконена (или вот ссылка), потом обойти его, найти самую глубокую вершину, у которой есть более одного ребенка, и вывести путь до нее от корня. Работает за O(n).

Edit:

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

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

Comments

[lexstile]

Благодарю за ответ, а вы не смогли бы третье решение описать чуть подробнее? Заранее благодарен.

[Wataru]

best_length = 0;
for (b1 = 0; b1 < n; ++b1) {
  for(b2 = b1+1; b2 < n; ++b2) {
     i = 0;
     // Если куски не могут пересекаться, то надо еще проверить, что b1+i<b2.
     while (b2+i < n && s[b1+i] == s[b2+i]) {
       ++i;     
     }
     if (i > best_length) {
       best_length = i;
       best_beg = b1;
     }
  }
}
// Вывести кусок с best_beg длиной best_length.

[lexstile]

wataru, большое спасибо!