Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой

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

(число повторов известно)

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

Найти: набор (n₁,...,n_M) Î Ω_M номеров такой, что

при ограничениях

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

O[M(N - q + 1)(T_max - T_min + q³)] = O(MN⁴) = O(N⁵),

обоснован в [4, 8].