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

На рис. 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.