Напомню, что подпоследовательность строки получается путем исключения из нее нуля или более символов, не обязательно смежных. Общая подпоследовательность двух строк - это строка, являющаяся подпоследовательностью каждой из них. Самая длинная из таких строк называется, понятное дело, самой длинной общей подпоследовательностью. Итак, задача состоит в том, чтобы для данных строк x и y (|x|, |y| > 0) найти |lcs(x,y)|, где lcs(x,y) - самая длинная общая подпоследовательность (longest common subsequence) x и y. Как правило, требуется найти не только длину lcs(x,y), но и саму эту последовательность. В этом разделе : 8  Введение Для начала определим, в чем заключается задача. 8  Рекурсивное решение Попробуем решить нашу задачу, используя рекурсию, а далее улучшить его через динамическое программирование. 8  Запоминание Недостаток рекурсивного решения в том, что одинаковые подзадачи вызываются много раз в разное время. 8  Динамическое программирование снизу вверх То, что было описано выше - всего лишь более умный путь создания рекурсивного алгоритма. Но можно считать эту программу способом заполнения массива L. Последовательность заполнения контролирует рекурсия, однако те же результаты можно получить и при другом порядке. 8  Итерационное LCS ( Longest Common Subsequence ) 8  Сама подпоследовательность 8  Уменьшаем требоватия к памяти Один из недостатков описанного метода динамического программирования, по сравнению с исходной рекурсией - в том, что он требует O(mn) памяти на массив L ( рекурсия - O(n+m) ).

8  Введение 8  Рекурсивное решение 8  Запоминание 8  Динамическое программирование снизу вверх 8  Итерационное LCS ( Longest Common Subsequence ) 8  Сама подпоследовательность 8  Уменьшаем требоватия к памяти