В данном задании необходимо реализовать алгоритм поиска наибольшей общей подпоследовательности, иногда называемый алгоритмом Ахо. Задание является обязательным для выполнения.
Динамическим программированием называется метод решения задач путем сведения их к аналогичным задачам меньшего размера, причем результаты решения этих задач сохраняются и используются для решения исходной задачи.
Многие рекурсивные алгоритмы с возвратом можно переписать динамически. Обычно такая реализация требует больше памяти, чем рекурсия (для хранения промежуточных значений), но работает заметно быстрее.
Рассмотрим следующую задачу. Даны две строки (последовательности символов) длиной
M и N соответственно. Необходимо найти наибольшую
общую подстроку этих двух строк. Например, для строк "abcd"
и "aacd" наибольшей подстрокой будет
строка "acd".
Попробуем разбить задачу на аналогичные подзадачи меньшего размера. Пусть даны
две строки s и t. Сравним последние символы этих строк.
Если они совпадают, то решением, очевидно, будет набольшая подстрока
для строк s без последнего символа и t без последнего символа,
к которой добавили тот самый совпадающий последний символ. Например, если
s = "abcd" и t = "aacd",
то решением задачи будет общая подстрока строк "abc" и
"aac" с добавленным к ней в конце символом d.
Если же последние символы не совпадают, то рассмотрим два варианта: отбросим последний символ сначала у одной строки, а затем у другой, и выберем наилучший из этих вариантов.
Ясно, что такой алгоритм легко реализуется рекурсивно. Однако, можно предложить более
хорошее решение. Построим матрицу A[M][N], в которой элемент A[i][j]
будет хранить длину наибольшей общей подстроки строки из первых i
символов s и первых j символов t. Другими словами,
A[i][j] — решение аналогичной задачи для двух строк длиной i
и j соответственно. Заполнить таблицу такими значениями легко, двигаясь
слева направо и сверху вниз: для каждой клетки (i, j) выполняем проверку:
s[i] = t[j], в клетку (i, j) поставим
увеличенное на единицу значение клетки (i – 1, j – 1).
Для строк "abcd" и "aacd" таблица будет
заполнена следующим образом:
| 0 | a | b | c | d |
| a | 1 | 1 | 1 | 1 |
| a | 1 | 1 | 1 | 1 |
| c | 1 | 1 | 2 | 2 |
| d | 1 | 1 | 2 | 3 |
По построению таблицы, в правом нижнем углу — длина наибольшей общей подстроки. Восстановить саму подстроку можно, «раскручивая» алгоритм в обратную сторону.
Во входном файле input.txt даны две строки. Выдать в выходной файл output.txt
их наибольшую общую подстроку.