Обратите внимание, что приведенный в листинге 12.24 метод требует постоянного времени для обработки двух строк, независимо от степени их совпадения или несовпадения. Если длина строк равна, соответственно, n и т, то время, требуемое для выполнения основного цикла, будет пропорционально произведению n * m, поскольку таковым является количество ячеек, значения которых нужно вычислить. (помните, что ячейка, для которой действительно нужно получить ответ - последняя, значение которой должно вычисляться;
она расположена в нижнем правом углу матрицы).
Алгоритм, реализованный с применением рекурсивного метода, приведен в листинге 12.25. Рекурсивная подпрограмма кодируется в виде функции, которая возвращает длину LCS для конкретной ячейки, заданной индексом строки и столбца (которые, в конечном счете, представляют собой индексы, указывающие на строки From и То).
Листинг 12.25. Рекурсивное вычисление LCS
function TtdStringLCS.slGetCell(aFromInx, aToInx : integer): integer;
var
LCSData : PtdLCSData;
NorthLen: integer;
WestLen : integer;
begin
if (aFromInx = 0) or (aToInx = 0) then
Result := 0
else begin
LCSData := FMatrix[ aFromInx, aToInx];
if (LCSData <> nil) then
Result := LCSData^.ldLen else begin
{создать новый элемент}
New(LCSData);
{если два символа совпадают, необходимо увеличить значение счетчика относительно элемента, расположенного к северо-западу от данного, т.е. предшествующего элемента}
if (FFromStr[aFromInx] = FToStr [aToInx]) then begin
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;
end
{в противном случае текущие символы различаются: необходимо использовать максимальный из элементов, расположенных к северу и западу (выбор элемента расположенного к западу предпочтительнее)}
else begin
NorthLen := slGetCell(aFromInx-1, aToInx);
WestLen := slGetCell(aFromInx, aToInx-1);
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev := ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить значение элемента матрицы}
FMatrix[aFromInx, aToInx] := LCSData;
{вернуть длину данной LCS}
Result := LCSData^.ldLen;
end;
end;
end;
Первое существенное различие состоит в том, что не нужно генерировать нулевые значения для ячеек, расположенных вдоль верхней и правой сторон матрицы. Теперь эту задачу выполняет простой оператор If. (Честно говоря, в итеративном варианте вычисления LCS можно было бы обойтись без вычисления этих значений, но в этом случае внутренний код цикла оказался бы значительно сложнее для понимания и поддержки. Поэтому для простоты мы заранее вычисляем значения этих ячеек.) Если значение ячейки уже вычислено, мы просто возвращаем ее длину LCS. Если нет, необходимо выполнить ту же проверку, что и в предыдущем случае: совпадают ли два символа? Если да, то необходимо добавить единицу к значению LCS ячейки, расположенной к северо-западу от данной. Если нет, необходимо использовать большее из значений длины LCS ячеек, расположенных к северу и к западу от текущей. Естественно, эти значения LCS вычисляются в результате рекурсивных вызовов этой подпрограммы.
Применив обе версии (итеративную и рекурсивную), я сгенерировал матрицу для вычисления LCS слов "illiteracy" и "innumeracy". (Длина LCS этих слов равна 6 и выглядит как "ieracy".) Результаты этих немалых трудов приведены в таблицах 12.2 и 12.3. При использовании рекурсивной версии многие ячейки вообще не вычисляются (они помечены знаком вопроса). Эти ячейки образуют часть заключительной LCS.
Таблица 12.2. Итеративная матрица LCS слов "illiteracy" и "innumeracy".