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

Пусть – последовательность символов .Последовательность называется подпоследовательностьюпоследовательности если она может быть получена из последовательности удалениемее некоторых элементов. Например, если – последовательность символов то последовательность состоящая из символов является подпоследовательностью так какона может быть получена с помощью удаления элементов

Подпоследовательность называется общей подпоследовательностьюпоследовательностей и если она является подпоследовательностью обеих последовательностей.Например, подпоследовательность является общей подпоследовательностью последовательностей и

Длиной последовательности(подпоследовательности) будем называть количество ее элементов.Например, длина последовательности равна 6.

Подпоследовательность называется наибольшейобщей подпоследовательностьюпоследовательностей и если имеет наибольшую длину среди всех общих подпоследовательностей.Например, общая подпоследовательность является наибольшей для последовательностей и В общем случае может быть несколько наибольшихподпоследовательностей. Например, тоже является наибольшей общей подпоследовательностью для последовательностей из последнего примера.Часто для обозначения наибольшей общей подпоследовательностииспользуется сокращение LCS(longestcommonsubsequence).

Рекурсивный алгоритм вычисления длины LCS для двух последовательностей и основывается на трех следующих очевидных утверждениях, которые приводятся без доказательства:

1. Если то и является LCSдля и

2. Если и то является LCSдля и

3. Если и то является LCSдля и

Обозначив через длину LCSдля последовательностей и можем записать следующее рекуррентное соотношение:

Рассмотрим пример вычисления длины LCSдляпоследовательностей и Вычисление осуществляется по шагам:

1) .

2)

3)

4) .

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)

20)

21)

22)

23)

24)

25)

26)

Все шаги вычисления можно разбить на две группы: с 1 по 17 и с 18 по26.Первая группасоответствует рекурсивному погружению, вторая – восходящему вычислению. Результатом вычисления является значение равное длине LCS. Нетрудно убедиться, чтодля последовательностей и существуют две LCS: и имеющих длину 3.

На рис.13 и 14 представленарекурсивная функция lcs, вычисляющая длину LCSдля двух заданных последовательностей, а на рис. 15 – пример программы, вызывающей эту функцию, и результат ее выполнения (рис. 16) соответственно.

Рис. 13.Прототип функцииlcs,вычисляющей длину LCSдля двух заданных последовательностей

Рис. 14. Реализацияфункции lcs

Рис. 15. Пример вызовафункции lcs

Рис. 16. Результат выполнения программы, представленной на рис. 15

Функцияlcsимеет четыре параметра: lenx (длина первой последовательности), x(массив, содержащий символы первой последовательности), leny (длина второй последовательности), x(массив, содержащий символы второй последовательности). Функция возвращает длину LCSзаданных последовательностей.

Функцияlcsфактически повторяет запись рекуррентного соотношения, записанного выше, и поэтому не требует дополнительного пояснения. Обратите внимание, что исходные последовательностии результат совпадают с последовательностями и результатом вычисления предыдущего примера.