Выбрать главу

Обратите внимание, что приведенный в листинге 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".