Решение задачи о наибольшей общей подпоследовательности

На рис. 8 и 9 представлена функция lcsd, реализующая алгоритм динамического программирования для решения задачи о наибольшей общей подпоследовательности (LCS).

Рис. 8. Прототип функции lcsd

Рис. 9. Реализация функции lcsd

Функция lcsd имеет три параметра: x (символьная строка, интерпретируемая как первая заданная последовательность), y (символьная строка, интерпретируемая как вторая заданная последовательность) и возвращаемый параметр z (символьная строка, интерпретируемая как LCS двух последовательностей, заданных первыми двумя параметрами). Функция возвращает длину LCS.

Для построения наибольшей общей подпоследовательности в функции lcsd используются два массива С и B. Массивы моделирует матрицы размерностью где – размерности соответственно первой и второй последовательностей. Номера строк матриц, начиная с первой, соответствуют номерам элементов первой последовательности, а номера столбцов, тоже начиная с первого, – номерам элементов второй последовательности. Дляудобства работы с массивами как с матрицами применяются два макроса: LCS_C и LCS_B.

Массив C предназначен для вычисления длины LCS. Элементы массива C – числа. Вычисление элементов C осуществляется пошагово, начиная с северо-западного угла матрицы. В результате вычислений в последней строке последнего столбца матрицы C (в юго-восточном углу) находится длина LCS.

Массив B предназначен для построения массива LCS (возвращаемый параметр z). Массив B моделирует матрицу, элементами которой могут быть три типа символов, обозначающих направления: TOP (вверх), LEFT (налево), LEFTTOP (налево и вверх). Заполнение матрицы B осуществляетсяодновременнозаполнением матрицы C и в том же порядке.

На рис. 10 изображены матрицы С и B после завершения работы алгоритма функции lcsd для двух последовательностей B, D, C, A, B, A и A, B, C, B, D, A, B.

Рис. 10. Заполненные матрицы C и B

Функция lcsd вызывает вспомогательную рекурсивную функцию getLCScontent,предназначенную для формирования строки LSC.

Функция имеет восемь параметров: lenx (длина первой последовательности), leny (длина второй последовательности), x (символьная строка, интерпретируемая как первая заданная последовательность), B (сформированный массив B), n (длина LCS), i (номер строки текущего элемента матрицы B), j (номер столбца текущего элемента матрицы B), а также возвращаемый параметр z (символьная строка, интерпретируемая как LCS двух последовательностей).

Функция getLCScontent выбирает элементы массива B,начиная с последнего элемента последней строки, используя значения выбранных элементов массива как указатель направления перехода к следующему элементу. На рис. 10 выбранные элементы массива B выделены. Выбранные элементы массива B,значение которых LEFTTOP (на рис. 10 – диагональная стрелка), соответствуют элементам последовательностей, вошедших в LSC.