Количество упорядоченных вхождений подпоследовательности

[Nikita_Danilov]

Добрый день, уважаемые знатоки!

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

Например, пусть дана последовательность: 1, 2, 1, 2, 1, 2, 3, 1, 2, 1.
Необходимо подсчитать количество вхождений подпоследовательности: 1, 2, 1.
Ответ: количество вхождений равно 2, т.к. 3й элемент относится к первой найденной подпоследовательности.

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

Глобально, пытаюсь адаптировать теорию последовательных шаблонов под новую область, где требуется расчет точной поддержки на уровне одной последовательности, а не просто факт поддерживается/нет.
Насколько нашел, в теории ассоциативных правил и последовательных шаблонов функция для поддержки просто указывается как sup(...), либо как некоторое значение, а дальше расшифровываются правила вычисления поддержки.
Но мне это не нравится, хочется описать всё одной функцией, чтобы удобнее было рассчитывать оптимизацию, хотя возможно я и заблуждаюсь, и оно мне не надо.

Буду благодарен любым мыслям в данном направлении!

[provincialka]

Хм... а что вы понимаете под "функцией"? В особенности "математической"? Какую-то формулу? И что в нее может входить? Многочлены? Логарифмы? Или, не дай бог, синусы?

[Nikita_Danilov]

provincialka в сообщении #1169350 писал(а):

Хм... а что вы понимаете под "функцией"? В особенности "математической"? Какую-то формулу? И что в нее может входить? Многочлены? Логарифмы? Или, не дай бог, синусы?

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

Глобально, мне потребуется составить целевую функцию для оптимизации, где будет использоваться в том числе и количество вхождений.
Насколько понял, целевая функция в принципе может описываться и в т.ч. с использованием предописанных функций типа sup(...), как в теории шаблонов, но с другой стороны, зачем разбивать описание, если получится всё соединить.

[arseniiv]

Здесь очень сильно стоит ожидать, что в лучшем случае выражение для функции будет точной записью алгоритма. Как я понимаю, люди обычно ожидают, что «функция» — это нечто более быстро считающееся, чем «алгоритм». На самом же деле, когда до таких мыслей доходит, надо просто разбираться, где можно и как нужно оптимизировать имеющийся код — или писать этот код, если его ещё нет. (Ну или ничего не делать, и просто не думать о ерунде.)

Если вам надо узнавать числа вхождений, когда последовательность или подпоследовательность фиксированы, то, кажется, были какие-то алгоритмы быстрее линейного от длин.

[Nikita_Danilov]

arseniiv в сообщении #1169353 писал(а):

На самом же деле, когда до таких мыслей доходит, надо просто разбираться, где можно и как нужно оптимизировать имеющийся код — или писать этот код, если его ещё нет. (Ну или ничего не делать, и просто не думать о ерунде.)

Выше вот немного уточнил, зачем мне это - для формальной постановки задачи с целевой функцией.
Родилась мысль, возможно ли полностью обойтись без пояснений для функции, включив в неё сразу всё необходимое.
UPD: Алгоритмы посмотрю, спасибо за мысль, существует и правда много интересных (даже хотя бы здесь описанных https://habrahabr.ru/post/111449/, http://algolist.manual.ru/search/esearch/), может чего придумается.

[arseniiv]

Nikita_Danilov в сообщении #1169354 писал(а):

Выше вот немного уточнил, зачем мне это - для формальной постановки задачи с целевой функцией.

Ну, с моей низкой колокольни не видно, чем тут может помешать то, что функцию удобнее описать реализующим её алгоритмом.

Потом, формально-то функция описывается вообще-то проще некуда. Вот у вас алфавит $A$, строка $\sigma\in A^*$, «тестовая подстрока» $\alpha\in A^+$. Максимальное $n$, для которого существуют строки $\gamma_0,\ldots,\gamma_n\in A^*$ такие что $\sigma = \gamma_0\alpha\gamma_1\alpha\ldots\alpha\gamma_n$, и есть значение интересующей функции. Это значение определно однозначно (разве что можно дописать, что для $n=0$ равенство выше имеет вид $\sigma=\gamma_0$ и всегда выполнимо). Можно придумать и другие, более изощрённые, определения — например, как число применений определённого правила определённой грамматики при порождении $\sigma$.

[Nikita_Danilov]

arseniiv в сообщении #1169359 писал(а):

Максимальное $n$, для которого существуют строки $\gamma_0,\ldots,\gamma_n\in A^*$ такие что $\sigma = \gamma_0\alpha\gamma_1\alpha\ldots\alpha\gamma_n$, и есть значение интересующей функции. Это значение определно однозначно (разве что можно дописать, что для $n=0$ равенство выше имеет вид $\sigma=\gamma_0$ и всегда выполнимо).

Спустя почти месяц, когда подошел вплотную к описанию этого блока у себя, я понял что это значит!
Спасибо! В принципе может этого и хватит, попробую сформировать мысль, посмотрю что скажет науч.рук.