Пусть – последовательность символов . Последовательность называется подпоследовательностью последовательности если она может быть получена из последовательности удалением ее некоторых элементов. Например, если – последовательность символов то последовательность состоящая из символов является подпоследовательностью так как она может быть получена с помощью удаления элементов
Подпоследовательность называется общей подпоследовательностью последовательностей и если она является подпоследовательностью обеих последовательностей. Например, подпоследовательность является общей подпоследовательностью последовательностей и
Длиной последовательности (подпоследовательности) будем называть количество ее элементов. Например, длина последовательности равна 6.
Подпоследовательность называется наибольшейобщей подпоследовательностью последовательностей и если имеет наибольшую длину среди всех общих подпоследовательностей. Например, общая подпоследовательность является наибольшей для последовательностей и В общем случае может быть несколько наибольших подпоследовательностей. Например, тоже является наибольшей общей подпоследовательностью для последовательностей из последнего примера. Часто для обозначения наибольшей общей подпоследовательности используется сокращение LCS (longest common subsequence).
|
|
Рекурсивный алгоритм вычисления длины 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 фактически повторяет запись рекуррентного соотношения, записанного выше, и поэтому не требует дополнительного пояснения. Обратите внимание, что исходные последовательности и результат совпадают с последовательностями и результатом вычисления предыдущего примера.