Здравствуйте, Sharov, Вы писали:

S>Если длина задача, то для каждой последовательности считаете вхождения пос-ти данной длины. Пусть длина 2, сначала 12, пргоняете по всем последовательном и считаете, потом 23, потом 34,42,23(возможно уже быда), 31 . По памяти О(1).

Как-то уж слишком брутфорсно получается, но ничего лучше я не могу тоже придумать.

Возможно, если задать отношение порядка для подпоследовательностей и искать вхождения подпоследовательностей от меньшей к большей, то можно избежать повторений.
Тогда будет выглядеть так:
За первый проход ищем минимальную подпоследовательность.
На следующих проходах считаем две величины: количество вхождений заданной подпоследовательности и следующую по порядку подпоследовательнось.

Но в пределе все равно квадрат, а для среднего что-то не могу вероятности сходу посчитать.