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

MVK>Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
MVK>сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.

Как мы запомним подпоследовательности из предыдущего К? Ведь память должна быть O(1)

MVK>Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
MVK>В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.

Что-то я запутался.
Пусть P — длина строки, N — количество строк. Превратить длину строки P в константу мы всегда сможем, а сейчас предлагаю ее учитывать.
Как работает алгоритм и какова его сложность?