Задача поиска последовательных шаблонов представляет
довольно сложную задачу.

Возьмём, к примеру, последовательность <(a₁,a₂);(a₃,a₄,a₅)>

и
попытаемся перебрать возможные варианты – мы получим их 39:

1) (a₁)

2) (a₂)

3) (a₁,a₂)

4) (a₃)

5) (a₄)

6) (a₅)

7) (a₃,a₄)

8) (a₃,a₅)

9) (a₄,a₅)

10) (a₃,a₄,a₅)

11) (a₁),
(a₃)

12) (a₂)
, (a₃)

13) (a₁,a₂)
, (a₃)

и т.д.

  Любой из этих вариантов может оказаться решением задачи и следовательно решение задачи представляется как полный перебор и составления в результате довольно большой базы данных (либо большие временный затраты на вычисления) для дальнейших вычислений.

 Попытаемся найти иной подход.

Пусть имеются две последовательности:

<(a₁,a₂);(a₃,a₄,a₅)>

<(b₁,b₂);(b₃,b₄,b₅,b₆),(b₇)>

 Возьмём в качестве a_i, b_j простые числа b и
составим из них произведения:

A=a_1*a_2*a_3*a_4*a₅

B=b_1*b_2*b_3*b_4*b_5*b_6*b₇

Найдём С=НОД(A,B).

  Ясно, что решение нашей (поставленной исходно) задачи в принятых обозначения будет состоять из делителей числа С.

И всё бы было хорошо, но при этом не учитывается порядок
следования событий.

  Например.

С= a_1*a₃ и a₁=b₁, a₃=b₂ ,

то решением задачи может быть только <(a₁)>.

Если же

С= a_1*a₃ и a₁=b₁, a₃=b₄ ,

то решением задачи могут быть уже следующие последовательности:

<(a₁)>,

<(a₂)>,

< (a₁); (a₂)>.

  Опять придётся делать перебор (теперь уже на соответствие исходному порядку следования), хотя он и гораздо меньше (для данной ситуации надо проверить3 последовательности вместо 39 . И всего будет 15 проверок, и даже меньше – 5, т.к. последовательности вида <(a_i)>, всегда допустимы).

 При более длинных последовательностях количество проверок может возрасти. Поэтому введём порядок для множителей.

  Будем возводить множители в степень, соответствующие их номеру набора, т.е. произведения

A=a_1*a_2*a_3*a_4*a₅

B=b_1*b_2*b_3*b_4*b_5*b_6*b₇

Преобразуются в

A=a₁¹_*a₂¹_*a₃²_*a₄²_*a₅²

B=b₁¹_*b₂¹_*b₃²_*b₄²_*b₅²_*b₆²_*b₇³

С=НОД(A,B).

  Пример.

a₁=b₁,
a₃=b₂ ,

С= a₁¹_*a₃²

Из полученного выражения, сразу ясно, что a₁ входит в первый набор как
первой, так и второй последовательности.

Полученное выражение (т.к. 2 не представляется как сумма двух различных положительных чисел) также говорит нам о том, что a₃ входит во второй набор как первой, так и второй последовательности.

Нам не требуется производить перебор вовсе.

  Пример.

 Допустим, мы получили
выражение:

  С= a₁¹_*a₃⁶

6=1+5=2+4.

Поэтому

С= a₁¹_*a₃⁶=
a₁¹_*a₃¹a₃⁵=
a₁¹_*a₃²a₃⁴

В том случае a₁
входит в первый набор как первой, так и второй последовательности.

Для а₃ возможны уже варианты:

- a₃ входит в шестой набор либо первой, либо второй последовательности.

- a₃ входит в первый и в пятый наборы либо первой, либо второй последовательности.

- a₃ входит во второй и в четвёртый наборы либо первой, либо второй
последовательности.

Сколько здесь проверок? – максимум 10.

Сколько проверок предполагает полный перебор?

 – если обе последовательности содержат не менее 6 наборов каждая (каждый набор содержит не менее одного числа), то

- из первой последовательности мы получаем как минимум количество вариантов:

6+5+4+3+2+1+4+3+2+1+3+2+1+2+1+1+3+2+1+2+1+1+2+1+1+1=11+14+12+8+5+6=59

- эти 59 вариантов мы должны проверить на вхождение во вторую последовательность, которая содержит, как минимум 6 наборов, т.е.
получаем 59*6=354 сравнений – и это минимум.

Таким образом мы получили произведение простых чисел, нахождение НОД и 10 проверок в замен, как минимум 354 проверки.

Что получается при добавлении новой последовательности в подобной ситуации?

- при работе с базой данных, возможные наборы из новой последовательности сравниваются с дополнительной базой данных – если грубо, то все 59 с каждым из элементом из базы.

- при подходе с использованием простых чисел можно также производить сравнение с базой данных и здесь получается нахождение НОД и 10 проверок на каждый элемент из базы.