Для нахождения максимальной подпоследовательности в строке можно использовать следующие алгоритмы:

• Перебор. 1 Например, перебрать все подпоследовательности первой строки и для каждой из них проверить, является ли она подпоследовательностью второй строки. 1
• Динамическое программирование. 12 С его помощью задачу можно решить за сложность O(nm). 1