Задача обнаружения повторяющегося набора эталонных фрагментов

(число фрагментов неизвестно)

Дано: вектор Y Î R^N,  набор (U₁,...,U_L) векторов из R^q, натуральные числа N^–, N⁺, T_min и T_max.  

Найти: оптимальное значение M и набор (n₁,...,n_M) Î Ω такие, что

где $$l(m|L) = (m-$1) mod$L+1; Y_n = (y_n,...,y_n+q-1),  n = 0,...,N - q.

Задача разрешима за полиномиальное время. Алгоритм, имеющий временную сложность

O[min{L, M_max}(N - q + 1)(T_max - T_min + q)] = O(min{L, M_max}N ²) = O(N ⁴),