Попробуем решить нашу задачу, используя рекурсию, а далее улучшить его через динамическое программирование. Для начала - несколько простых наблюдений. Пусть у нас есть две строки, например 'nematode knowledge' и 'empty bottle'. Тогда мы можем представить подпоследовательность как способ записи этих строк так, что определенные буквы будут одна под другой: n e m a t o d e [пробел] k n o w l e d g e | | | | | | | e m p t y [пробел] b o t t l e Если мы обозначим такие совпадения линиями, то никакие две из них не пересекутся. Вообще, любой непересекающийся набор линий будет давать подпоследовательность. Из этого мы можем вывести следующий простой факт: если две строки начинаются с одной буквы, то мы всегда можем выбрать ее первым символом подпоследовательности. С другой стороны, если, как в примере выше, два первых символа различны, то они не могут быть частью общей подпоследовательности. Итак, мы решили, что делать с первыми символами, а значит у нас осталась только 'подзадача' - найти наибольшую общую подпоследовательность уже двух меньших строк. Таким образом имеем рекурсию. Вместо нахождения самой наибольшей подпоследовательности, можно узнать ее длину. Тогда, если первые два символа разные, мы обнаружим, какая подзадача дает верное решение, решив их обе и взяв максимальную из получившихся подпоследовательностей. А, воспользовавшись динамическим программированием, мы увидим, как найти саму подпоследовательность. Итак, эти наблюдения дают нам следующий, пока неэффективный, рекурсивный алгоритм: Рекурсивное решение: int lcs_length(char * A, char * B) { if (*A == '\0' || *B == '\0') return 0; else if (*A == *B) return 1 + lcs_length(A+1, B+1); else return max(lcs_length(A+1,B), lcs_length(A,B+1)); } Этот алгоритм будет работать, однако он требует слишком много времени. Если в двух строках нет совпадающих символов, то время оценивается биномиальными коэффициентами, которые ( при m=n ) близки к 2n.  8  Комментарии к статье  8 8  Обсудить в чате