Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 347

Однако прежде чем приступить к рассмотрению просмотра матрицы LCS, необходимо ее построить. Пока же будем считать, что в каждом элементе матрицы будут храниться два информационных фрагмента: длина LCS на данном этапе и позиция предыдущего элемента матрицы, образующего предшественницу этой LCS. Для последнего значения существует только три возможных ячейки: непосредственно над ним (к северу), слева (к западу) и выше и левее (к северо-западу). Поэтому для их обозначения вполне можно было бы использовать перечислимый тип.

Давайте вручную вычислим LCS для случая строк BEGIN/FINISH. Мы получим матрицу 6x7 (мы будем учитывать пустые подстроки, поэтому индексация должна начинаться с 0). Вместо того, чтобы рекурсивно заполнять матрицу (все эти рекурсивные вызовы трудно поддерживать в упорядоченном виде), итеративно вычислим все ячейки слева направо и сверху вниз. Вычисление ячеек первой строки и первого столбца не представляет сложности: они все являются нулями. Почему? Да потому, что наиболее длинная общая последовательность пустой и любой другой строки равна нулевой строке. С этого момента можно начать определение LCS для ячейки (1,1) или двух строк B и F. Два последних символа этих односимвольных строк не совпадают. Следовательно, длина LCS равна максимальной из предшествующих ячеек, расположенных к северу и к западу от данной. Обе эти ячейки нулевые, поэтому их максимальное значение и, следовательно, значение этой ячейки равно нулю. Ячейка (1,2) соответствует строкам B и F1. Ее значение также рано нулю. Ячейка (2,1) соответствует строкам BE и F: длина LCS снова равна 0. Продолжая подобные вычисления, можно заполнить все 42 ячейки матрицы. Обратите внимание на ячейки, соответствующие совпадающим символам: именно в них длина LCS возрастает. Конечный результат показан в таблице 12.1.

Таблица 12.1. Матрица LCS для строк BEGIN и FINISH

_ _ F I N I S H

_ 0 0 0 0 0 0 0

B 0 0 0 0 0 0 0

E 0 0 0 0 0 0 0

G 0 0 0 0 0 0 0

I 0 0 1 1 1 1 1

N 0 0 1 2 2 2 2

Записать этот процесс выполнения действий вручную в виде кода не особенно трудно. Чтобы облегчить задачу начинающим программистам, я решил вначале создать класс матричного кеша. Внутри этого класса матрица хранится в объекте TList из TLists, причем ведущий объект TList представляет строки в матрице, а ведомый TLists - ячейки в столбцах отдельной строки. Кроме того, класс матрицы специфичен для решаемой задачи. Было бы излишним разрабатывать, кодировать и использовать общий класс матрицы. Код реализации класса матрицы показан в листинге 12.22.

Листинг 12.22. Класс матрицы для реализации алгоритма определения LCS

type

TtdLCSDir = (ldNorth, ldNorthWest, ldWest);

PtdLCSData = ^TtdLCSData;

TtdLCSData = packed record

ldLen : integer;

ldPrev : TtdLCSDir;

end;

type

TtdLCSMatrix = class private

FCols : integer;

FMatrix : TList;

FRows : integer;